3
$\begingroup$

My question was partly inspired by the question linked below.

I see a wonderful construction of Adam P. Goucher, which guarantees that 3-connected 5-regular planar graphs are infinitely numerous. I wonder if there is a similar construct for the 5-connected 5-regular planar graphs. (Maybe I don't need to generate all of them like the title of this post.)

enter image description here

I noted the number of 5-connected 5-regular planar graphs with at most 36 vertices in the following paper.

  • Hasheminezhad M, McKay B, Reeves T. Recursive generation of simple planar 5-regular graphs and pentangulations[J]. 2011.

enter image description here

Enough such graphs to convince me there are an unlimited number of such graphs. And when $n$ is large enough, for every $n$ there is a graph that I want.

Improve this question
$\endgroup$
2
  • $\begingroup$ Surely the exact same construction works? $\gcd(16-2,18-2) = 2$ and the Frobenius number of 7 and 8 is 41 so there's a graph for any even $n \ge 86$. $\endgroup$
    – Peter Taylor
    Commented Jun 15, 2022 at 14:26
  • $\begingroup$ Unfortunately, I'm not sure if the same construction can keep the new graph 5-connected. $\endgroup$
    – Licheng Zhang
    Commented Jun 15, 2022 at 14:32

1 Answer 1

Reset to default
5
$\begingroup$

The answer is yes.

This construction is from the paper "Pairs of Hamiltonian circuits in 5-connected planar graphs" by Joseph Zaks. This is the "connected sum" of a 5-regular planar graph with an icosahedral graph.

graph substitution

Let $G$ be a 5-valent 5-connected planar graph and $v$ a vertex of it. Replace $v$ by the 11-vertex graph shown above. The new graph is 5-valent, 5-connected, planar and has 10 more vertices. Thus there is an infinitude of such graphs.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .