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\}$?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Check out the split decomposition of a graph. en.wikipedia.org/wiki/Split_(graph_theory) $\endgroup$– Tony HuynhJul 10, 2017 at 15:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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]$.
answered Oct 11, 2016 at 11:16
-
$\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$– asmaOct 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$– asmaOct 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$– VictorOct 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$– VictorOct 23, 2016 at 12:16