<p><a href="https://math.stackexchange.com/questions/4563760/local-equivalency-of-ring-graphs-and-2xn-grid-graphs/4565862#4565862">Link to answer by</a> <a href="https://math.stackexchange.com/users/383078/misha-lavrov">Misha Lavrov</a></p>
<p>Bouchet's paper <a href="https://doi.org/10.1016/0012-365X(93)90357-Y" rel="nofollow noreferrer">Recognizing locally equivalent graphs</a> gives an invariant that can be used to show that for <span class="math-container">$n &gt; 4$</span>, the <span class="math-container">$2 \times n$</span> grid graph is <strong>not</strong> locally equivalent to <span class="math-container">$R_{2n}$</span>, the ring graph on <span class="math-container">$2n$</span> vertices. (I usually call this graph the cycle graph <span class="math-container">$C_{2n}$</span>, but I'll try to stick with the question's notation here.)</p>
<p>If <span class="math-container">$F$</span> is a graph and <span class="math-container">$X$</span> is a subset of <span class="math-container">$V(F)$</span>, then Bouchet defines <span class="math-container">$o(X,F)$</span> to be the number of induced subgraphs of <span class="math-container">$F$</span> whose set of odd vertices is precisely <span class="math-container">$X$</span>. Statement 3.1 in the paper is that</p>
<blockquote>
<p>If <span class="math-container">$F$</span> and <span class="math-container">$F'$</span> are locally equivalent graphs on the vertex set <span class="math-container">$V$</span>, then <span class="math-container">$o(X,F) = o(X,F')$</span> holds for every <span class="math-container">$F, F' \subseteq V$</span>.</p>
</blockquote>
<p>(For Bouchet, graphs are locally equivalent if we can transform one into the other <em>exactly</em>; in this question, we want to transform the <span class="math-container">$2 \times n$</span> grid graph into a graph <em>isomorphic</em> to <span class="math-container">$R_{2n}$</span>, so we allow permuting <span class="math-container">$V$</span> as well.)</p>
<p>If <span class="math-container">$G$</span> is the <span class="math-container">$2 \times n$</span> grid graph</p>
<pre><code>2 --- 4 --- ... --- 2n
|     |              |
|     |              |
1 --- 3 --- ... --- 2n-1
</code></pre>
<p>then the set of vertices <span class="math-container">$X = \{3,4,5,6,\dots,2n-3,2n-2\}$</span> has <span class="math-container">$o(X,G) \ge 1$</span> since, in particular, <span class="math-container">$X$</span> is the set of odd vertices of <span class="math-container">$G$</span> itself.</p>
<p>If this grid graph can be turned into any graph <span class="math-container">$G'$</span> isomorphic to the ring graph <span class="math-container">$R_{2n}$</span>, then we must have <span class="math-container">$o(X,G') \ge 1$</span>, which means that after permuting the vertices, we have <span class="math-container">$o(X', R_{2n}) \ge 1$</span> for <em>some</em> set <span class="math-container">$X'$</span> of cardinality <span class="math-container">$2n-4$</span>.</p>
<p>However, three consecutive vertices <span class="math-container">$i,i+1,i+2$</span> of <span class="math-container">$R_{2n}$</span> cannot ever be odd vertices in any induced subgraph all at the same time. (If they are odd vertices in <span class="math-container">$R_{2n}[Y]$</span> for some <span class="math-container">$Y \subseteq V(R_{2n})$</span>, then in particular we must have <span class="math-container">$i, i+1, i+2 \in Y$</span>; but then, the degree of <span class="math-container">$i+1$</span> in <span class="math-container">$R_{2n}[Y]$</span> is <span class="math-container">$2$</span>, which is even.) Averaging over all consecutive triples, we see that at most <span class="math-container">$\frac23$</span> of the vertices can be odd in any induced subgraph. It follows that <span class="math-container">$o(X', R_{2n}) = 0$</span> whenever <span class="math-container">$|X'| &gt; \frac23 \cdot 2n$</span>. If <span class="math-container">$n &gt; 6$</span>, then <span class="math-container">$2n-4 &gt; \frac23 \cdot 2n$</span>, so Bouchet's invariant proves that the <span class="math-container">$2\times n$</span> grid graph cannot be locally equivalent to <span class="math-container">$R_{2n}$</span>.</p>
<hr />
<p>We can finish off the question for <span class="math-container">$n=5$</span> and <span class="math-container">$n=6$</span> by computing <span class="math-container">$f(G) = o(\varnothing, G)$</span>: the number of even induced subgraphs of <span class="math-container">$G$</span>. Since the empty set is left unchanged by all permutations of <span class="math-container">$V(G)$</span>, <span class="math-container">$f(G)$</span> is an invariant of local equivalence up to isomorphism.</p>
<p>By a direct computation in Mathematica:</p>
<ul>
<li>When <span class="math-container">$G$</span> is the <span class="math-container">$2\times 3$</span> grid graph and <span class="math-container">$G' = R_6$</span>, <span class="math-container">$f(G) = f(G') = 19$</span>, so things are good here.</li>
<li>When <span class="math-container">$G$</span> is the <span class="math-container">$2\times 4$</span> grid graph and <span class="math-container">$G' = R_8$</span>, <span class="math-container">$f(G) = f(G') = 48$</span>, so things are still good. This confirms that our invariant doesn't prove anything false - always good to check!</li>
<li>When <span class="math-container">$G$</span> is the <span class="math-container">$2\times 5$</span> grid graph and <span class="math-container">$G' = R_{10}$</span>, <span class="math-container">$f(G) = 120$</span> but <span class="math-container">$f(G') = 124$</span>, so <span class="math-container">$G$</span> is not locally equivalent to <span class="math-container">$G'$</span>.</li>
<li>When <span class="math-container">$G$</span> is the <span class="math-container">$2\times 6$</span> grid graph and <span class="math-container">$G' = R_{12}$</span>, <span class="math-container">$f(G) = 299$</span> but <span class="math-container">$f(G') = 323$</span>, so <span class="math-container">$G$</span> is not locally equivalent to <span class="math-container">$G'$</span>.</li>
</ul>
<p>In fact, it's probably possible to get formulas for <span class="math-container">$f(G), f(G')$</span> and use it to solve all cases; I believe that the numbers are <a href="https://oeis.org/A295045" rel="nofollow noreferrer">A295045</a> for the grid graphs and <a href="https://oeis.org/A065034" rel="nofollow noreferrer">A065034</a> for the ring graphs. However, proving this seems harder than the approach taken earlier.</p>

CC BY-SA 4.0
2022-11-04T09:04:41.840Z
To clarify -- this is a verbatim copy of the answer https://math.stackexchange.com/a/4565862
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-11-04T05:41:09.733Z
2022-11-04T05:41:09.733Z
Dotman
<blockquote>
<p>(<strong>Local complementation</strong>) A local complementation <span class="math-container">$\tau_v$</span> is a graph operation specified by a vertex <span class="math-container">$v$</span>, taking a graph <span class="math-container">$G$</span> to <span class="math-container">$\tau_v(G)$</span> by replacing the induced subgraph on the neighborhood of <span class="math-container">$v$</span>, i.e. <span class="math-container">$G\left[N_v\right]$</span>, by its complement. The neighborhood of any vertex <span class="math-container">$u$</span> in the graph <span class="math-container">$\tau_v(G)$</span> is therefore given by
<span class="math-container">$$
N_u^{\left(\tau_v(G)\right)}= \begin{cases}N_u \Delta\left(N_v \backslash\{u\}\right) &amp; \text { if }(u, v) \in E(G), \\ N_u &amp; \text { otherwise.}\end{cases}
$$</span></p>
<p>(<strong>Ring graph</strong>) The ring graph on <span class="math-container">$n$</span> vertices, <span class="math-container">$R_n$</span>, may be viewed as having a vertex set corresponding to the integers modulo <span class="math-container">$n$</span>. In this case, we view the vertices as the numbers 0 through <span class="math-container">$n-1$</span>, with edges <span class="math-container">$(i, i+1)$</span>, computed modulo <span class="math-container">$n$</span>.</p>
</blockquote>
<p>I was playing with grid graphs and found that the <span class="math-container">$2\times 3$</span> and <span class="math-container">$2\times4$</span> grid graphs are related to ring graphs via some sequence of local complementations.</p>
<p><a href="https://i.sstatic.net/tqObD.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/tqObD.png" alt="enter image description here" /></a></p>
<p>For the above <span class="math-container">$2\times3$</span> grid graph, local complementation on vertex 1 followed by one on 2 and then again on 1; LC(1)LC(2)LC(1); gives a
ring graph,</p>
<p><a href="https://i.sstatic.net/qet9O.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qet9O.png" alt="enter image description here" /></a></p>
<p>Similarly,</p>
<p><a href="https://i.sstatic.net/zHVmp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/zHVmp.png" alt="enter image description here" /></a></p>
<p>can be converted to a ring graph via LC(1)LC(2)LC(1) LC(8)LC(7)LC(8)</p>
<p><a href="https://i.sstatic.net/XmHL0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XmHL0.png" alt="enter image description here" /></a></p>
<p>I was hoping to find such relationships between ring graphs and <span class="math-container">$2\times n $</span> grid graphs. My hope is that for any <span class="math-container">$n$</span>, <span class="math-container">$2\times n$</span> grid graphs can be converted to ring graphs via some sequence of local complementations. Even if not as a concrete answer, please point me toward relevant research articles, if you can.</p>
<p>EDIT</p>
<p>The answer to this question can be found <a href="https://math.stackexchange.com/questions/4563760/local-equivalency-of-ring-graphs-and-2xn-grid-graphs/4565862#4565862">here</a>.</p>

CC BY-SA 4.0
2022-10-27T10:02:58.920Z
https://cstheory.stackexchange.com/q/52002/67196 @a3nm
Dotman
CC BY-SA 4.0
2022-10-28T10:57:26.603Z
have you tried exhaustive search on $n=5$, either by computer or by hand? after a small unsuccessful attempt by myself, it seemed that such a solution might give a hint for a general strategy.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-10-28T13:18:59.567Z
I haven't tried an exhaustive search. But I have found some packages online for searching such local equivalences. I have been trying to get it running since yesterday.
Dotman
CC BY-SA 4.0
2022-10-28T13:19:07.583Z
https://github.com/AckslD/vertex-minors
Dotman
CC BY-SA 4.0
2022-11-01T13:23:47.047Z
I see the problem -- interesting. What is the status of the earlier question https://cstheory.stackexchange.com/questions/52002/vertex-minors-of-ring-graphs then? Also, is anything known in general about the equivalence relation on graphs defined as rewritability by this local complementation operation?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-11-01T15:36:48.813Z
@a3nm Well there's and its not what I wanted https://math.stackexchange.com/questions/4563760/local-equivalency-of-ring-graphs-and-2xn-grid-graphs/4565862#4565862
Dotman
CC BY-SA 4.0
2022-11-01T15:44:56.770Z
Ah, OK, the question was also posted on Math.SE, but then can you clarify the status of your two questions here (e.g., answering them yourself) to avoid confusion to future visitors? Thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-11-01T15:46:52.380Z
I'm not sure. I think I'll delete the old question and answer this myself.
Dotman
CC BY-SA 4.0
2022-11-03T15:35:59.877Z
Dotman, thanks -- instead of editing the question, you can then post an answer to this question with the link to the other question.
Antoine Amarilli 'a3nm'
<graph-theory><graph-algorithms><graph-isomorphism><planar-graphs>
2xn grid graphs from ring graphs via local complementations
Dotman
# 2xn grid graphs from ring graphs via local complementations

(Asked by: username_0 on 2022-10-27)

> (**Local complementation**) A local complementation $\tau\_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau\_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, i.e. $G\left[N\_v\right]$, by its complement. The neighborhood of any vertex $u$ in the graph $\tau\_v(G)$ is therefore given by
> $$
> N\_u^{\left(\tau\_v(G)\right)}= \begin{cases}N\_u \Delta\left(N\_v \backslash\{u\}\right) & \text { if }(u, v) \in E(G), \\ N\_u & \text { otherwise.}\end{cases}
> $$
>
> (**Ring graph**) The ring graph on $n$ vertices, $R\_n$, may be viewed as having a vertex set corresponding to the integers modulo $n$. In this case, we view the vertices as the numbers 0 through $n-1$, with edges $(i, i+1)$, computed modulo $n$.

I was playing with grid graphs and found that the $2\times 3$ and $2\times4$ grid graphs are related to ring graphs via some sequence of local complementations.

[![enter image description here](https://i.sstatic.net/tqObD.png)](https://i.sstatic.net/tqObD.png)

For the above $2\times3$ grid graph, local complementation on vertex 1 followed by one on 2 and then again on 1; LC(1)LC(2)LC(1); gives a
ring graph,

[![enter image description here](https://i.sstatic.net/qet9O.png)](https://i.sstatic.net/qet9O.png)

Similarly,

[![enter image description here](https://i.sstatic.net/zHVmp.png)](https://i.sstatic.net/zHVmp.png)

can be converted to a ring graph via LC(1)LC(2)LC(1) LC(8)LC(7)LC(8)

[![enter image description here](https://i.sstatic.net/XmHL0.png)](https://i.sstatic.net/XmHL0.png)

I was hoping to find such relationships between ring graphs and $2\times n $ grid graphs. My hope is that for any $n$, $2\times n$ grid graphs can be converted to ring graphs via some sequence of local complementations. Even if not as a concrete answer, please point me toward relevant research articles, if you can.

EDIT

The answer to this question can be found [here](https://math.stackexchange.com/questions/4563760/local-equivalency-of-ring-graphs-and-2xn-grid-graphs/4565862#4565862).

**Tags:** graph-theory, graph-algorithms, graph-isomorphism, planar-graphs

> **Comments:**
> **username_0**: https://cstheory.stackexchange.com/q/52002/67196 @a3nm  
> **username_1**: have you tried exhaustive search on $n=5$, either by computer or by hand? after a small unsuccessful attempt by myself, it seemed that such a solution might give a hint for a general strategy.  
> **username_0**: I haven't tried an exhaustive search. But I have found some packages online for searching such local equivalences. I have been trying to get it running since yesterday.  
> **username_0**: https://github.com/AckslD/vertex-minors  
> **username_2**: I see the problem -- interesting. What is the status of the earlier question https://cstheory.stackexchange.com/questions/52002/vertex-minors-of-ring-graphs then? Also, is anything known in general about the equivalence relation on graphs defined as rewritability by this local complementation operation?  
> **username_0**: @a3nm Well there's and its not what I wanted https://math.stackexchange.com/questions/4563760/local-equivalency-of-ring-graphs-and-2xn-grid-graphs/4565862#4565862  
> **username_2**: Ah, OK, the question was also posted on Math.SE, but then can you clarify the status of your two questions here (e.g., answering them yourself) to avoid confusion to future visitors? Thanks!  
> **username_0**: I'm not sure. I think I'll delete the old question and answer this myself.  
> **username_2**: username_0, thanks -- instead of editing the question, you can then post an answer to this question with the link to the other question.  

---

## 1 answers

### Answer by username_0 on 2022-11-04. Score: 2 | Accepted answer

Link to answer by Misha Lavrov
Bouchet's paper Recognizing locally equivalent graphs gives an invariant that can be used to show that for $n > 4$, the $2 \times n$ grid graph is not locally equivalent to $R_{2n}$, the ring graph on $2n$ vertices. (I usually call this graph the cycle graph $C_{2n}$, but I'll try to stick with the question's notation here.)
If $F$ is a graph and $X$ is a subset of $V(F)$, then Bouchet defines $o(X,F)$ to be the number of induced subgraphs of $F$ whose set of odd vertices is precisely $X$. Statement 3.1 in the paper is that

If $F$ and $F'$ are locally equivalent graphs on the vertex set $V$, then $o(X,F) = o(X,F')$ holds for every $F, F' \subseteq V$.

(For Bouchet, graphs are locally equivalent if we can transform one into the other exactly; in this question, we want to transform the $2 \times n$ grid graph into a graph isomorphic to $R_{2n}$, so we allow permuting $V$ as well.)
If $G$ is the $2 \times n$ grid graph
2 --- 4 --- ... --- 2n
|     |              |
|     |              |
1 --- 3 --- ... --- 2n-1

then the set of vertices $X = \{3,4,5,6,\dots,2n-3,2n-2\}$ has $o(X,G) \ge 1$ since, in particular, $X$ is the set of odd vertices of $G$ itself.
If this grid graph can be turned into any graph $G'$ isomorphic to the ring graph $R_{2n}$, then we must have $o(X,G') \ge 1$, which means that after permuting the vertices, we have $o(X', R_{2n}) \ge 1$ for some set $X'$ of cardinality $2n-4$.
However, three consecutive vertices $i,i+1,i+2$ of $R_{2n}$ cannot ever be odd vertices in any induced subgraph all at the same time. (If they are odd vertices in $R_{2n}[Y]$ for some $Y \subseteq V(R_{2n})$, then in particular we must have $i, i+1, i+2 \in Y$; but then, the degree of $i+1$ in $R_{2n}[Y]$ is $2$, which is even.) Averaging over all consecutive triples, we see that at most $\frac23$ of the vertices can be odd in any induced subgraph. It follows that $o(X', R_{2n}) = 0$ whenever $|X'| > \frac23 \cdot 2n$. If $n > 6$, then $2n-4 > \frac23 \cdot 2n$, so Bouchet's invariant proves that the $2\times n$ grid graph cannot be locally equivalent to $R_{2n}$.

We can finish off the question for $n=5$ and $n=6$ by computing $f(G) = o(\varnothing, G)$: the number of even induced subgraphs of $G$. Since the empty set is left unchanged by all permutations of $V(G)$, $f(G)$ is an invariant of local equivalence up to isomorphism.
By a direct computation in Mathematica:

When $G$ is the $2\times 3$ grid graph and $G' = R_6$, $f(G) = f(G') = 19$, so things are good here.
When $G$ is the $2\times 4$ grid graph and $G' = R_8$, $f(G) = f(G') = 48$, so things are still good. This confirms that our invariant doesn't prove anything false - always good to check!
When $G$ is the $2\times 5$ grid graph and $G' = R_{10}$, $f(G) = 120$ but $f(G') = 124$, so $G$ is not locally equivalent to $G'$.
When $G$ is the $2\times 6$ grid graph and $G' = R_{12}$, $f(G) = 299$ but $f(G') = 323$, so $G$ is not locally equivalent to $G'$.

In fact, it's probably possible to get formulas for $f(G), f(G')$ and use it to solve all cases; I believe that the numbers are A295045 for the grid graphs and A065034 for the ring graphs. However, proving this seems harder than the approach taken earlier.

> **Comments:**
> **username_2**: To clarify -- this is a verbatim copy of the answer https://math.stackexchange.com/a/4565862  

---

