# H-generalized join graph

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]$.

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