# Graph transformation related to graph isomorphism

Basically got graph transformation related to graph isomorphism.

Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$.

Edges of $G'$.

(1) Add $(v_i,e_j)$ iff $v_i \in e_j$. This graph is bipartite and is the subdivision of $G$. According to a paper this preserves GI.

(2) Make a clique of $v'$ vertices, i.e. add $(v_i,v_j)$ for $i \ne j$ and without multiple edges. This graph is chordal and split and according to paper preserves GI.

(3) Make a clique of $e'$ vertices, i.e. add $(e_i,e_j)$ for $i \ne j$ and without multiple edges.

Vertices of $G'$ can be partitioned into two cliques on $v',e'$ and the edges between the cliques are from (1), are the subdivision of $G$.

$G \cong H \implies G' \cong H'$.

Q1 Does this transformation preserves isomorphism? $G' \cong H' \implies G \cong H$?

I am inclined to believe so, since the cliques doesn't matter much and the subdivision subgraph of (1) preserves isomorphism.

A graph is $X$-free if it doesn't contain induced subgraph $X$.

Claim 1. $G'$ is $(P_4 \cup K_1)$-free.

$3$ or more $v'$ vertices induce triangle and $3$ or more $e'$ vertices induce triangle since they are in a clique. The $5$ vertices of $(P_4 \cup K_1)$ can't be partitioned in $v',e'$ without a triangle.

Is this correct?

Conjecture based on experimental data and suggested proof:

If $G$ is triangle-free, $G'$ is $\overline{3K_2}$-free. $\overline{3K_2}=K_{2,2,2}$ and the clique number is $3$, so if induced $\overline{3K_2}$ would exists it must be on $3e' \cup 3v'$ vertices. I suspect that the $v'$ vertices must induce triangle in $G$ for the following reason: The partitions of $K_{2,2,2}=\overline{3K_2}$ are $(v_1,e_1),(v_2,e_2),(v_3,e_3)$. The edges $(v_i,v_j),(e_i,e_j)$ come from the cliques. The remaining edges are $(v_1,\{e_2,e_3\}),(v_2,\{e_1,e_3\}),(v_3,\{e_1,e_2\})$, which is $C_6$, subdivision of triangle, contradicting triangle-free.

Counterexamples are welcome.

For triangle-free $G$, $G'$ is $(P_4 \cup K_1,\overline{3K2})$-free.

Appears to me correctness of the above and paper top of p. 10 would imply GI is in P.

• $Q_1$ should be a direct consequence of the following 2 lemmas: given two bipartite graphs $G=(V_1\cup V_2,E), G' =(V'_1\cup V'_2,E')$ then (1) they are isomorphic if and only if their complements are isomorphic. (2) the operation of "complementing the edges" of a bipartite graph (i.e. replacing all the edges $E$ with all the edges $(u,v) \notin E, u \in V_1, v \in V_2$) preserves isomorphism. I'll check it better and convert it to an answer. – Marzio De Biasi Jul 12 '14 at 11:32
• Also claim 1 seems correct: to avoid a triangle two nodes of $P_4$ must be on the clique from $V_1$ and the other two on the clique from $V_2$. So there is no way to pick the $K_1$. You can tight it: $G'$ is also $(P_3 \cup K_1)$ free. – Marzio De Biasi Jul 12 '14 at 12:02
• @MarzioDeBiasi edited with proposed proof of the conjecture, do you object it? – joro Jul 12 '14 at 12:48
• no problem! I tried to read the last part of the question but I got totally lost. What is the relation of the claims in your question and theorem 6 of the paper? I think you should 1) briefly define what are $\overline{3K_2}$, and $K_{2,2,2}$; 2) write the theorem of the paper; 3) briefly explain why the claims of your question and the theorem lead to GI in P – Marzio De Biasi Jul 12 '14 at 18:48

Here is a proof that the answer to Q1 is yes.

Let $f$ be the described transformation and suppose that $G'=f(G)$ for some $G$. Let $A$ and $B$ be the vertices of $G'$ that correspond to the vertices and edges of $G$ respectively. Note that $(A,B)$ is a partition of $V(G')$ such that $A$ is a clique, $B$ is a clique and each vertex in $B$ has exactly two neighbours in $A$. Call such a partition good.

Claim. $G'$ has a unique good partition unless $G$ is a star or $2$-regular.

Proof. Let $(A',B')$ be a good partition different from $(A,B)$. Write $A'=A_1 \cup B_1$ and $B'=A_2 \cup B_2$ where $A_1 \cup A_2=A$ and $B_1 \cup B_2=B$. First suppose that for some $i$, both $A_i$ and $B_i$ are non-empty. Since, $A_i \cup B_i$ is a clique, it follows that $B_i$ are the edges of a star, and $A_i=\{x\}$ where $x$ is the middle vertex of this star. Since the claim obviously holds if $|V(G)| \leq 2$, the only remaining possibilities are

1. $(A',B')=(B,A)$, or
2. $|A_1|=1$ and $B_2=\emptyset$, or
3. $|A_2|=1$ and $B_1=\emptyset$.

The third possibility is impossible since the vertices in $B_2$ would only have one neighbour in $A'$. The first possibility implies that $G$ is $2$-regular, and the second possibility implies that $G$ is a star. This completes the proof of the claim.

Note the above proof shows that if $G$ is $2$-regular or a star, then $G'$ has exactly two good partitions. For a good partition $(A,B)$ let $G'(A,B)$ be the graph obtained by removing the edges of the cliques on $A$ and $B$. If $G'$ has two good partitions $(A,B)$ and $(A',B')$, it is easy to see (and somewhat magical) that $G'(A,B) \cong G'(A',B')$. Therefore, we can recover $G$ from $G'$ by finding a good partition $(A,B)$ and computing $G'(A,B)$ (this will be the graph obtained from $G$ by subdividing every edge once).

• Thanks. So your answer, claim 1, the suggested proof imply for triangle free G, G' is $(P_4 \cup K1,\overline{3K_2})$-free. According to the linked paper GI for this class is in P, so this implies GI is in P or am I missing something? – joro Jul 13 '14 at 9:07
• Why you need find good partition? YOU are computing the transformation so you know the partitions. My sage code finds the partitions even for 2-regular. Or am I missing something? – joro Jul 13 '14 at 9:28
• The reason this answers Q1 is the following. Suppose I give you a graph $G'$ and tell you that it comes from some $G$, but I don't tell you which $G$. A priori it might even be that $G'$ comes from two non-isomorphic graphs. But the answer shows that one can in fact recover $G$ from $G'$. – Tony Huynh Jul 13 '14 at 14:54
• Thanks. Do you have opinion about the graph class described in the linked paper and this question: mathoverflow.net/questions/176016/… – joro Jul 13 '14 at 16:26