# 2xn grid graphs from ring graphs via local complementations

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

EDIT

The answer to this question can be found here.

• Oct 27, 2022 at 10:02
• 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. Oct 28, 2022 at 10:57
• 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. Oct 28, 2022 at 13:18
• github.com/AckslD/vertex-minors Oct 28, 2022 at 13:19
• I see the problem -- interesting. What is the status of the earlier question cstheory.stackexchange.com/questions/52002/… then? Also, is anything known in general about the equivalence relation on graphs defined as rewritability by this local complementation operation?
– a3nm
Nov 1, 2022 at 13:23

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.