Join operation and graph isomorphism.

85 Views Asked by At

The join of two graphs $G_1$ and $G_2$, denoted by $G_1 \nabla G_2 $, is a graph obtained from $G_1$ and $G_2$ by joining each vertex of $G_1$ to all vertices of $G_2$. We write $G_1\cong G_2$ for that $G_1$ is isomorphic to $G_2$.

I believe the following statement is correct, but I am unable to provide a rigorous proof at the moment.

Assertion 1. Let $G$ and $H$ be graphs. Then $G\cong H$ if and only if $(G \nabla K_1) \cong (H \nabla K_1)$ where $K_1$ is a single vertex.

Furthermore, the statement below is to be considered.

Assertion 2. Let $G$, $H$ and $F$ be graphs. Then $G\cong H$ if and only if $(G \nabla F) \cong (H \nabla F)$.

Maybe these two assertions are incorrect. At the moment, I haven't come up with counterexamples. Perhaps someone has proven the statements in somewhere.

1

There are 1 best solutions below

0
On BEST ANSWER

Both assertions are correct. It is perhaps easier to see this by taking complements: note that $G\cong H$ if and only if $\overline G\cong \overline H$, and that $\overline{G\mathbin{\nabla} H}=\overline G \mathbin{\dot \cup} \overline H$, where $\dot \cup$ is disjoint union, so each assertion is equivalent to the corresponding statement for disjoint union.

Then if $G \mathbin{\dot \cup} F\cong H \mathbin{\dot \cup} F$ they both have the same number of components isomorphic to each fixed graph, and the original graphs $G$ and $H$ are obtained by removing one component (or a disjoint union of several components, if $F$ is disconnected) isomorphic to $F$.