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

<p>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.</p>

<p>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$.</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-06-23T13:32:45.413Z
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
CC BY-SA 3.0
2014-06-23T13:50:19.427Z
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
CC BY-SA 3.0
2014-06-23T13:22:30.863Z
2014-06-23T13:45:47.493Z
2014-06-23T13:45:47.493Z
Marzio De Biasi
<p>The transformation replacing an edge by a graph gadget
is widely used in graph theory.</p>

<p>As an example, <a href="https://cstheory.stackexchange.com/a/24882/3247">in an answer</a> Marzio De Biasi subdivided
edges which increases the girth while preserving GI.</p>

<p>A gadget $GA$ is a graph with two distinguished vertices $u,v$.</p>

<p>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.</p>

<blockquote>
  <p>Which gadgets $GA$ preserve isomorphism:  $G \cong H \iff G' \cong H'$</p>
</blockquote>

<p><strong>Added to clarify</strong></p>

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

<p><strong>Added 2</strong> I am interested when $GA$ is fixed (and possibly small).</p>

CC BY-SA 3.0
2014-06-23T10:45:26.737Z
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 :-)
Marzio De Biasi
CC BY-SA 3.0
2014-06-23T10:46:44.970Z
@MarzioDeBiasi Will edit. Assume $GA$ is small and fixed.
joro
CC BY-SA 3.0
2014-06-23T12:12:09.360Z
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)$.
Marzio De Biasi
CC BY-SA 3.0
2014-06-23T12:31:52.567Z
@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.
Peter Shor 
CC BY-SA 3.0
2014-06-23T12:45:23.630Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2014-06-23T12:54:18.137Z
@MarzioDeBiasi I edited with clarification about the construction. You might misunderstand the construction of the gadget.
joro
CC BY-SA 3.0
2014-06-23T13:25:31.847Z
@joro: ok, I summarized my comments in an answer that takes into account your definition (the single distinguishing node obviously doesn't work). I'm still checking it.
Marzio De Biasi
<graph-theory><graph-algorithms><graph-isomorphism>
When replacing an edge with a graph gadget preserves graph isomorphism?
joro
# When replacing an edge with a graph gadget preserves graph isomorphism?

(Asked by: username_0 on 2014-06-23)

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

As an example, [in an answer](https://cstheory.stackexchange.com/a/24882/3247) 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'$

**Added to clarify**

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

**Tags:** graph-theory, graph-algorithms, graph-isomorphism
> **Comments:**
> **username_1**: 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 :-)  
> **username_0**: @MarzioDeBiasi Will edit. Assume $GA$ is small and fixed.  
> **username_1**: 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)$.  
> **username_2**: @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.  
> **username_1**: @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.  
> **username_0**: @MarzioDeBiasi I edited with clarification about the construction. You might misunderstand the construction of the gadget.  
> **username_1**: @joro: ok, I summarized my comments in an answer that takes into account your definition (the single distinguishing node obviously doesn't work). I'm still checking it.  

---

## 1 answers

### Answer by username_1 on 2014-06-23. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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 ?  

---

