0
$\begingroup$

(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

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

Similarly,

enter image description here

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

enter image description here

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.

$\endgroup$
9
  • $\begingroup$ cstheory.stackexchange.com/q/52002/67196 @a3nm $\endgroup$
    – Dotman
    Oct 27, 2022 at 10:02
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 28, 2022 at 10:57
  • $\begingroup$ 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. $\endgroup$
    – Dotman
    Oct 28, 2022 at 13:18
  • $\begingroup$ github.com/AckslD/vertex-minors $\endgroup$
    – Dotman
    Oct 28, 2022 at 13:19
  • $\begingroup$ 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? $\endgroup$
    – a3nm
    Nov 1, 2022 at 13:23

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.