What is the range of possible values for the length of a cycle in a 3-connected pentagulation?

291 Views Asked by At

Edits: Parcly Taxel first discovered that the length of cycle cannot be constrained by the 3-connected condition. However, I think the construction proposed by kabenyuk later is wonderful. Therefore, I choose it as the best answer. But this does not mean that Parcly Taxel's construction is not excellent.

A pentagulation is a planar graph whose faces are all of length five; see the following Figure, for example.

enter image description here

My question is:

What is the range of possible values for the length of a cycle in a 3-connected pentagulation?

First, We can find some special values by making some specific observations. For example, $5$-cycles, $8$-cycles, $9$-cycles. But for any integer $i\ge 3$, does there always exist a 3-connected pentagulation that contains a cycle $C_i$?

Note that we can easily see that in any 3-connected planar graph, any two faces can share at most one edge. So the following cases will not occur.

enter image description here

2

There are 2 best solutions below

1
On BEST ANSWER

Let us prove that for any integer $k\geq8$ there exists a 3-connected pentagulation with a cycle of length $k$.

First, how can we construct a 3-connected pentagulation with a large number of vertices. To do this, take the dodecahedral graph and put a new dodecahedral graph inside some face of it. This process can go on as long as you like.

Now consider three cases.

  1. Let $k=3s+2=4+3(s-2)+4$. Choose a sufficiently large 3-connected pentagulation and in it consider a chain of $s$ faces where each face has exactly one edge in common with its neighbor. The edges of this chain give a cycle of length $3s+2$.
  2. Let $k=3s$. Choose a chain of $s-1$ faces. Then add to the first face of this chain a face that has by one common edge with two adjacent faces of our chain.
  3. Let $k=3s+1$. If $s\geq5$, then it is similar to case 2. The cases $k=10$ and $k=13$ are special.

The figure illustrates the cases $k=20,21,22$. Inside each face there is the number of edges of that face included in the cycle.

enter image description here

Addendum.

I find it useful to give another universal reasoning.

  1. First note that the interior of a triangle can be divided into pentagons as shown in the figure.

enter image description here

Now let's inscribe in each of the three pentagons the dodecahedral graph. Let us call this graph $P$. The graph $P$ is a planar $3$-connected graph.

Another way to partition a triangle into pentagons can be found here (we will call it $Q$). For completeness, here is the $Q$ figure.

enter image description here

  1. Now let $C_k$ ($k\geq3$) be an arbitrary cycle whose vertices form a regular $k$-gon in the plane. Triangulate the interior and exterior of this cycle. Then in each triangle we inscribe graph $P$ or $Q$. The result is a $3$-connected pentagulation with cycle $C_k$.

Note of February 21. I corrected one inaccuracy in my answer.

One more remark. In point 1 it is actually enough to inscribe the dodecahedral graph into only two of the three pentagons, the result is a graph with $37$ vertices, which is isomorphic to the graph $Q$.

5
On

Consider the graphs formed from $3$ or more copies of the $12$-vertex fragment shown, forming a circular strip, and where every third vertex on the top side is connected to one new vertex and every third vertex on the bottom side is connected to another new vertex. It is easy to verify that these graphs are $3$-connected pentangulations, and that sufficiently long strips contain $C_k$ for all $k\ge8$:

The remaining cycle lengths are also attainable. The graphs on the extreme left and right below are 3-connected pentangulations except for a hexagon or heptagon face; joining two copies of either along this odd face (and in the heptagon case rotating so that no degree-$2$ vertices are in the result) produces a true pentangulation with a $C_6$ or $C_7$ respectively. For $C_3$ and $C_4$ add the correct graph on the right side to the hexagon and perform the doubling construction.

In summary, all cycle lengths are attainable.