Local equivalency of ring graphs and 2xn grid graphs

Question

This question has also been posted in theoretical computer science stack exchange

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

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,

Similarly,

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

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.

Answer 1

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.