1
$\begingroup$

The diameter of graph is the maximum distance between the pair of vertices.

From the article we know that there is no planar graph of diameter 2 with minimal degree 5. (Thank kabenyuk for informing me of this result in the previous post.)

Today, I want to shift my focus to the construction of planar graphs with minimum degree $5$ (or 5-connected planar graphs) and diameter $3$. For planar graphs with minimum degree $5$ (and even $5$-connected), I can find some isolated examples to show that their diameter can be $3$. For example: Icosahedral Graph, or

![enter image description here

enter image description here

However, I haven't yet found a class of such $n$-order planar graphs of minimum degree $5$ (and even $5$-connected) with diameter $3$, where $n$ can be sufficiently large.

Are they finite in number or infinite?

$\endgroup$

1 Answer 1

4
$\begingroup$

One possible construction is a silly generalization of the icosahedron.

Start with the skeleton graph of an arbitrarily large antiprism: two $k$-sided polygons connected by a zigzagging strip of $2k$ triangles. Here, every vertex has degree $4$.

Then, add two more vertices, one in the middle of each length-$k$ face. The old vertices now have degree $5$, and the two new vertices have degree $k$. So, for all $k \ge 5$, this gives us a $(2k+2)$-vertex planar graph with minimum degree $5$. (When $k=5$, that graph is the skeleton graph of the icosahedron.)

A new vertex is at distance $1$ from each vertex of the length-$k$ face it was placed in, at distance $2$ from each vertex of the opposite length-$k$ face, and at distance $3$ from the other new vertex.

An old vertex is at distance at most $2$ from each other vertex of the same length-$k$ face, by going through the new vertex they're both adjacent to. So an old vertex is at distance at most $3$ from each other vertex of the opposite length-$k$ face (we start by going to a neighbor on the opposite face, and then finish as above). Therefore the diameter is $3$.

Here is a diagram of the $k=10$ case. It is not drawn in a planar fashion, because I see no clean way to do that, but you can imagine moving one of the central vertices (the one to the left, specifically) to the outside and drawing lots of curved edges.

enter image description here


If we want to generalize to an odd number of vertices, we can do that. In one of the length-$k$ faces, instead add two vertices with an edge between them, each adjacent to half of the length-$k$ face. (We can do slightly more than half, really; e.g. when $k=6$, each of the two vertices can be adjacent to $4$ out of $6$ vertices on the length-$6$ face.) This graph has $2k+3$ vertices, still has diameter $3$, and for $k \ge 6$ it has minimum degree $5$.

The $(2k+2)$-vertex construction gives us all even $n \ge 12$, and the $(2k+3)$-vertex construction gives us all odd $n\ge 15$. Therefore an $n$-vertex graph is achievable for all $n \ge 12$ except for $n=13$. On the other hand, a planar graph with minimum degree $5$ must have at least $12$ vertices of degree exactly $5$, so $n<12$ is impossible, and Plantri tells me that there are no $13$-vertex planar graphs with minimum degree $5$ at all! So the construction above covers all the values of $n$ we could have hoped for.


While we're at it, let's check the connectivity.

The antiprism graph is $4$-connected. To see this, suppose only $3$ vertices are deleted from the antiprism. Then one of the two length-$k$ faces only loses a single vertex, so it is still connected. Every vertex in the other face is adjacent to two vertices of the first face, at least one of which was not deleted, so it is also part of that connected component. Therefore deleting $3$ vertices does not disconnect the antiprism.

Both the odd and the even constructions above are $5$-connected. To see this, suppose only $4$ vertices are deleted from the graph. There are two cases:

  • If only $3$ vertices from the antiprism (and $1$ extra vertex) are deleted, then the antiprism is still connected. Each remaining extra vertex has at least $4$ neighbors in the antiprism, at least one of which survives, so each extra vertex is still connected to the antiprism, and the whole graph is connected.
  • If all $4$ deleted vertices are from the antiprism, then in particular all the extra vertices remain, ensuring that each side of the antiprism is connected. We can find a matching of size $k$ between the two sides of the antiprism, and $k \ge 5$, so at least one edge of that matching survives, connecting the two sides and therefore the whole graph.
$\endgroup$
2
  • $\begingroup$ +1. Thank you very much for your answer, as always, it's great. However, I have another question. How is the connectivity of the graphs you constructed? Are they all 5-connected? $\endgroup$
    – licheng
    Commented Apr 12, 2023 at 3:03
  • 1
    $\begingroup$ They are - I've added a proof of that. $\endgroup$ Commented Apr 12, 2023 at 3:20

You must log in to answer this question.

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