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


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.

  • $\begingroup$ sorry, I cant see how replacement product is related my notion. can you please explain your idea little bit. $\endgroup$ – GA316 Feb 12 '16 at 3:56
  • $\begingroup$ I think that your construction is called the lexicographic product of graphs, where in your case $G^ := G \cdot K_m$. $\endgroup$ – TheNicanova Feb 12 '16 at 4:01
  • $\begingroup$ "By joining of two graphs G1G1 and G2G2, I mean introducing edges between all the vertices of G1G1 to all the vertices of G2G2 and viz. and keeping the original edges as it is." This is exactly the definition of the lexicographic product (also called graph composition). $\endgroup$ – TheNicanova Feb 12 '16 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.