3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ $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. $\endgroup$ – Marzio De Biasi Jul 12 '14 at 11:32
  • $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Jul 12 '14 at 12:02
  • $\begingroup$ @MarzioDeBiasi edited with proposed proof of the conjecture, do you object it? $\endgroup$ – joro Jul 12 '14 at 12:48
  • $\begingroup$ 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 $\endgroup$ – Marzio De Biasi Jul 12 '14 at 18:48
1
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – joro Jul 13 '14 at 9:07
  • $\begingroup$ 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? $\endgroup$ – joro Jul 13 '14 at 9:28
  • $\begingroup$ 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'$. $\endgroup$ – Tony Huynh Jul 13 '14 at 14:54
  • $\begingroup$ Thanks. Do you have opinion about the graph class described in the linked paper and this question: mathoverflow.net/questions/176016/… $\endgroup$ – joro Jul 13 '14 at 16:26

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.