The $A$-join of a set of graphs $\{ G_a \}_{a \in A}$ as‎ ‎the graph $H$ with vertex and edge sets‎ ‎\begin{eqnarray*}‎ ‎V(H) &=& \{(x,y) \ | \ x \in V(A) \ \& \ y \in V(G_x) \},\\‎ ‎E(H) &=& \{ (x,y)(x^\prime,y^\prime) \ | \ xx^\prime \in E(A) \ ‎\text{or} \ x = x^\prime \ \& \ yy^\prime \in E(G_x)\}‎. ‎\end{eqnarray*}‎ ‎This graph is obtained by replacing each vertex $a \in V(A)$‎ ‎by the graph $G_a$ and inserting either all or none of the‎ ‎possible edges between vertices of $G_a$ and $G_b$ depending‎ ‎on whether or not $a$ and $b$ are joined by an edge in‎ ‎$A$‎. ‎If $ A $ is labeled and has $p$ points‎, ‎then the $A$-join of‎ ‎$H_1‎, ‎H_2‎, ‎\cdots‎, ‎H_p$ is denoted by $ A[H_1,H_2,\cdots‎, ‎H_p]$‎. Let $A[K_{a_1},K_{a_2},\cdots‎, K_{a_p}]\cong B[K_{b_1},K_{b_2},\cdots‎, K_{b_q}]$ where $K_{a_i}$ and $K_{b_i}$ are complete graphs. Is it true that from above isomorphic, can be concluded that $A\cong B$ and $\{a_1,a_2,\cdots ,a_p\}=\{b_1,b_2,\cdots, b_q\}$?


No we cannot conclude that $A$ and $B$ are isomorphic, and even when $A$ and $B$ are isomorphic it does not follow that $\{a_1, \dots, a_p\} = \{b_1, \dots, b_p\}$.

Notice that if $A = K_p$, then $A[K_{a_1}, \dots, K_{a_p}] = K_{a_1 + \cdots + a_p}$. So, if $A = K_2 = B$, then $K_2[K_2, K_2] = K_2[K_3, K_1]$. Also consider $A = K_2 \uplus K_2$ and $B = K_3 \uplus K_1$, then for example $A[K_1, K_2, K_2, K_2] = B[K_1, K_1, K_1, K_4]$.

  • $\begingroup$ If $A-$join and $B-$join are not complete graphs and graphs $A$ and $B$ are connected, then is it true?or is there counterexample? $\endgroup$ – asma Oct 12 '16 at 9:13
  • $\begingroup$ @asma, I do not know the answer with those new condition, but I will think about it. $\endgroup$ – John Machacek Oct 17 '16 at 1:33
  • $\begingroup$ Thanks. This answer is very important for me if you think about it. $\endgroup$ – asma Oct 23 '16 at 10:39
  • $\begingroup$ @asma this statement doesn't hold even when $A$ and $B$ are non-complete and connected. As a counterexample consider $A$ being a graph obtained from a triangle by adding a vertex adjacent to exactly one vertex of the triangle; $B$ being a path on three vertices. Now, in the graph $A$ substitute every vertex of the triangle by $K_2$ and the pendant vertex by $K_1$; in the graph $B$ substitute one of the ends of the path by $K_4$, the other end by $K_1$, and the central vertex by $K_2$. The resulting graphs are isomorphic, although, the original graphs are not. $\endgroup$ – Victor Oct 23 '16 at 11:53
  • $\begingroup$ I also suspect that the statement may be true when $A$ and $B$ are prime graphs. This is because if you substitute the vertices of a $p$-vertex prime graph $A$ by graphs $H_1, \ldots, H_p$, then in the resulting graph $A'$ the sets $V(H_1), \ldots, V(H_p)$ are precisely the maximal modules of $A'$. Since $A$ is prime, both $A'$ and the complement of $A'$ are connected. Hence, $A'$ admits a unique decomposition into maximal modules. Further, since $B'$ is isomorphic to $A'$, it also has a unique decomposition into maximal modules, which coincides with the decomposition of $A'$. $\endgroup$ – Victor Oct 23 '16 at 12:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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