2
$\begingroup$

Consider a $5$-regular undirected planar graph with $n$ vertices (a $k$-regular graph has exactly $k$ edges emanating from every node.)

Let us say we apply an arbitrary sequence (of length $\text{poly}(n)$ for some polynomial in $n$) of the following two transformations on this graph on whatever vertices we choose.

Vertex deletion: we delete a vertex, and all edges which have that vertex as an end point.

Neighborhood flip (also called local complementation): consider the set of all neighbors $N$ of some vertex $v$ (a neighbor is a vertex $u$ such that $(u, v)$ is an edge.) For all pairs of vertices in $N$, if any two vertices in $N$ are already connected by an edge, delete that edge. Else, connect the vertices.

Does there exist a $5$-regular undirected planar graph such we reach the $k \times k$ $2$D grid graph from it, using the above two transformations, for some $k \geq \Omega(n)$?


I did some trial and error and found no such example.

The problem is, the grid graph is planar, but the neighborhood flip operation does not necessarily preserve planarity. Additionally, it does not seem to be possible to reach the grid graph just by vertex deletion.

What might be a mathematical proof that there is no such example?

Note that if we are allowed to start from a non-planar $5$-regular graph, there are many examples such that we reach the grid in the end.

For simplicity, in case it helps, you may assume we are starting from a simple graph.

$\endgroup$

1 Answer 1

3
$\begingroup$

There are $5$-regular graphs with $O(k^2)$ vertices from which we can reach the $k \times k$ grid graph using only vertex deletion.

The grid graph has $k^2$ vertices and $2k(k-1)$ edges; to make it $5$-regular by adding edges (I know that's not what you want, but bear with me) we would need to add $\frac12 k^2 + 2k$ edges. I will assume $k$ is even so that this is an integer.

If we are okay with getting a planar multigraph at the end, then this is straightforward. In the $(k-2) \times (k-2)$ interior, double the edges of a perfect matching: now all the interior vertices go up from degree $4$ to $5$. Add a loop at every boundary vertex: now the sides go up from degree $3$ to $5$, and the corners from degree $2$ to $4$. Finally, add two edges that go between the corners.

Now, replace every edge $xy$ we added by the following gadget: an icosahedral graph (a planar $5$-regular graph with $12$ vertices) in which an edge $vw$ is deleted and replaced by edges $vx$, $wy$. Replace every loop at a vertex $x$ by a similar gadget, but with edge $vw$ deleted and replaced by edges $vx, wx$.

The result is a $5$-regular planar graph with $12 \left(\frac12k^2 + 2k\right)$ extra vertices on top of the vertices in the grid graph. In other words, it's a $5$-regular planar graph with $7k^2+24k$ vertices from which we can delete $6k^2+24k$ vertices and get a $k \times k$ grid graph.

$\endgroup$
3
  • $\begingroup$ Thanks! This looks very elegant and generalizable to argue about $k$-regular graphs, for any $k$. A question out of curiosity. I notice the construction results in a planar, regular, degree-$5$ graph, which isn't bipartite. However, the grid graph is bipartite. Is there some construction that preserves bipartite-ness (but results in a planar, regular, degree-$5$ graph still)? $\endgroup$ Mar 2 at 22:47
  • 1
    $\begingroup$ We can do essentially the same thing and get a bipartite multigraph. First, in the step where we add edges to the grid graph to make it a $5$-regular multigraph, make sure to only add edges that keep it bipartite (and no loops). This should still be doable, especially since we can add the same edge multiple times. Second, in place of the icosahedral graph, use a bipartite $5$-regular planar graph. $\endgroup$ Mar 3 at 3:03
  • $\begingroup$ Okay, looking back on that comment, it is vacuously true, but there is a much better answer: there are no bipartite $5$-regular planar graphs. (In an $n$-vertex bipartite planar graph, the number of edges is at most $2n-4$; in an $n$-vertex $5$-regular graph, the number of edges is $2.5n$.) $\endgroup$ Jul 20 at 14:54

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.