What is the terminology for assigning $K_{m_i}$ (complete graph) to the $i$ th vertex, 'joining' if the corresponding vertices are adjacent?

Question

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G{'}$ by considering the complete graph $K_{m_i}$ for each vertex i and 'join' (in the sense of graph theory) two of such complete graphs if the corresponding vertices are adjacent. Is there a name for this graph $G{'}$ associated to the Graph $G$?

By joining of two graphs $G_1$ and $G_2$, I mean introducing edges from all the vertices of $G_1$ to all the vertices of $G_2$ and vice versa, keeping the original edges as is.

Thanks for your valuable time.

Thanks a lot

Answer 1

I am not exactly sure of how your construction works, but I would start looking here. The lexicographic product might be what you are looking for. Hope this helps.

Answer 2

My approach to finding "terminology" for this construction, replacing the $n$ vertices of given graph $G$ with cliques of varying sizes, was to search the literature for examples (and report what authors have chosen for terminology).

The varied sizes of cliques highlighted in this Question seemed particularly unmotivated. A paper which uses a fixed clique size in replacing all vertices is Clique-inserted-graphs and spectral dynamics of clique-inserting by Zhang, Chen and Chen (2009). But their term "clique-inserted graphs" could well be applied to the more general construction (allowing different clique sizes for each vertex $v\in G$).

A proof requiring just such variable sized cliques is described in the Wikipedia article on the perfect graph theorem of László Lovász (1972), settling a conjecture by Claude Berge (1961,1963):

Given a perfect graph $G$, Lovász forms a graph $G*$ by replacing each vertex $v$ by a clique of $t_v$ vertices, where $t_v$ is the number of distinct maximum independent sets in G that contain $v$.

A footnote to the Wikipedia article says, "We follow here the exposition of the proof by Reed (2001)." The terminology used by Reed (cf. Chapter 2, From Conjecture to Theorem) concerning the replacement of a vertex by a clique is easier to segregate than in Lovász:

Definition 2.16 We replicate a vertex $x$ in a graph $G$ by adding a vertex $x'$ adjacent to $x + N(x)$.

As Reed observes, "We can perform [substituting a clique for a vertex] by a series of replications."

Finally let me point out that in the recently proposed duplicate target, Is there a name for Chain of complete bipartite graphs?, the setup calls for parts $V_k$ of the graph which are independent sets, so it is inconsistent with the notion of parts that are cliques.