# When replacing an edge with a graph gadget preserves graph isomorphism?

The transformation replacing an edge by a graph gadget is widely used in graph theory.

As an example, in an answer Marzio De Biasi subdivided edges which increases the girth while preserving GI.

A gadget $GA$ is a graph with two distinguished vertices $u,v$.

The transformation $G,GA \to G'$ is: replace edge $(x,y)$ in $G$ by a copy of the gadget $GA$ and in the copy set $u=x,v=y$ so $x,y$ from the original graph are the same in all copies.

Which gadgets $GA$ preserve isomorphism: $G \cong H \iff G' \cong H'$

I am looking for an algorithm given $GA,u,v$ to decide if it preserves isomorphism or not (reductions to GI complete problems are allowed though better be avoided).

Added 2 I am interested when $GA$ is fixed (and possibly small).

• marziodebiasi[at]gmail.com. Furthermore, this is a possible idea to prove that given $GA, u, v$, deciding if $GA$ preserves isomorphism is $GI$-complete: Given $G_1 = (V_1, E_1), G_2 = (V_2, E_2)$ build $GA$ in the following way: start adding four nodes $u,v,x,y$ and edges $(u,x),(x,y),(y,v)$, then add an edge from $x$ to all the nodes of $V_1$, and an edge from $y$ to all the nodes of $V_2$. I'll think more about it, after lunch :-) Jun 23 '14 at 10:45
• @MarzioDeBiasi Will edit. Assume $GA$ is small and fixed.
– joro
Jun 23 '14 at 10:46
• As sketched above, if the input of your decision problem (algorithm) is the triple $(GA,u,v)$, then the problem is GI-complete. If GA is fixed then the problem is obviously decidable in $O(1)$. Jun 23 '14 at 12:12
• @Marzio: If the OP is only interested in the case where GA is small, then an exponential-time algorithm would be practical. It's not clear to me that it's easy to find such an algorithm. Jun 23 '14 at 12:31
• @PeterShor: I think it's enough to test if $(X,u)\cup GA\cup (v,Y)$ is isomorphic to $(Y,u) \cup GA \cup (v,X)$; where $X$ is a star with a central node $x$ (connected to $u$ of GA) and $n$ neighbours (with $n > maxdeg(GA)$) and $Y$ is a star with a central node $y$ (connected to $v$ of GA) and $n+1$ neighbours. Jun 23 '14 at 12:45

Just a summary of my (very informal / wrong?) comments/ideas above:

Every connected gadget $GA$ with two or more nodes, that doesn't introduce an asymmetry between $u$ and $v$ should be fine. In other words suppose $maxdeg(GA)=n$, and that $X$ is a star with a central node $x$ and $n+1$ leaves, $Y$ is a star with a central node $y$ and $n+2$ leaves.

The $GA$ preserves isomorphism if and only if the two graphs $X \cup GA \cup Y$, in which $x$ is replaced with $u$ and $y$ is replaced with $v$, is isomorphic to the graph $Y \cup GA \cup X$ in which $y$ is replaced with $u$ and $x$ is replaced with $v$.

This construction can also be used to check if a small fixed $GA$ preserves isomorphism.

Furthermore, the problem of deciding if $(GA,u,v)$ preserves isomorphism is GI-complete: given two graphs $G_1,G_2$; build the following gadget $GA$: add 4 new nodes $u,x,y,v$ and edges $(u,x),(x,y),(y,v)$, then add an edge from $x$ to all the nodes of $G_1$ and an edge from $y$ to all the nodes of $G_2$. $G_1,G_2$ are isomorphic if and only if $GA$ preserves isomorphism.

• Thanks. I think gadgets exist for which G' and H' are isomorphic while G and H are not. Specific counterexample with u=0,v=1 and edges: [(0, 2), (0, 4), (0, 6), (1, 3), (1, 5), (1, 7), (2, 4), (2, 6), (3, 5), (3, 7), (4, 6), (5, 7)]. It satisfies your answer I believe.
– joro
Jun 23 '14 at 13:32
• Lol, you might be correct. The gadget is disconnected, didn't notice this. I thought about your approach, but the faulty gadget confused me :( Isn't your approach a special case of GI which preserves (non-proper) coloring ?
– joro
Jun 23 '14 at 13:50