EXACT PROFILE VALUES OF SOME GRAPH COMPOSITIONS
Yung‐Ling Lai · Taiwanese Journal of Mathematics · 2002
It is known that the determination of the profile for arbitrary graphs is NP-complete. The {\em composition } of two graphs $G$ and $H$ is the graph with vertex set $V(G)\times V(H)$ and $(u_1,v_1)$ is adjacent to $(u_2,v_2)$ if either $u_1$ is adjacent to $u_2$ in $G$ or $u_1=u_2$ and $v_1$ is adjacent to $v_2$ in $H$. The exact values of the profile of the composition of a path with other graphs, a cycle with other graphs, a complete graph with other graphs and a complete bipartite graph with other graphs are established.