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\}$?


1 Answer 1


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, 2016 at 9:13
  • $\begingroup$ @asma, I do not know the answer with those new condition, but I will think about it. $\endgroup$ Oct 17, 2016 at 1:33
  • $\begingroup$ Thanks. This answer is very important for me if you think about it. $\endgroup$
    – asma
    Oct 23, 2016 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, 2016 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, 2016 at 12:16

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.