5
$\begingroup$

Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory".

6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. Barcume proved that no such graph has more than 12 vertices.)

What is the original reference for Barcume's result, and how can it be proven?

PS: Another interesting observation is that upon reviewing the book's solution, I found the first example to be incorrect as its diameter is 4, not 3.

enter image description here

Misha Lavrov's answer is nice. By the way, for all (e.g., 10-vertex) 3-reguler planar graphs with diameter 3, we can also use nauty:

geng 10 -d3 -D3 | planarg | pickg -Z3

Similarly, we can call Nauty in Mathematica.

nauty = "D:\\nauty_win\\";
stream = 
  OpenRead[
   "! " <> nauty <> "geng 10 -d3 -D3 | " <> nauty <> "planarg | " <> 
    nauty <> "pickg -Z3"];
output = 
 Reap[While[(line = ReadLine[stream]) =!= EndOfFile, 
    Sow[ImportString[line, "Graph6"]]]][[2, 1]]

enter image description here

But now I do not understand the statement from Misha Lavrov: each one has a vertex not incident on an edge in X. For example, we chose $X=\{\{2,7\},\{3,8\}\}$. Then $V(G_1)=\{2,3,5,6\}$ and $V(G_2)=\{1,4,7,8\}$. But each vertex in $G_i$ is incident on an edge in $X$. Do I miss something? (Now, I understand; see the comments below the answer)

enter image description here

$\endgroup$
6
  • 1
    $\begingroup$ It looks like Troy Barcume (also mentioned in the acknowledgements) has (co-)authored only one paper, "On the Decomposition of Graphs Into Cliques", which I cannot access but which seems off-topic for this claim. So I doubt that the proof is published anywhere. $\endgroup$
    – Misha Lavrov
    Sep 18 at 15:11
  • 2
    $\begingroup$ On the other hand, the table here eventually led me to this paper, which I'll wait to post an answer about in case its author would like to do that first. $\endgroup$
    – Misha Lavrov
    Sep 18 at 15:25
  • $\begingroup$ Ars Comb. recently reopened, but it quickly closed again. Previously, it only offered a print edition, which means many articles are unavailable online. See math.stackexchange.com/questions/4327006/…. It's hard to imagine how the magazine is being managed; it's quite perplexing. In fact, there are some good articles inside. $\endgroup$
    – licheng
    Sep 19 at 3:10
  • $\begingroup$ @MishaLavrov This is weird, the bounds in this table seem far from optimal, the Moore bound gives an upper bound of 27306 for $\Delta = 5$ and $D = 8$ $\endgroup$
    – caduk
    Sep 19 at 13:14
  • 1
    $\begingroup$ @MishaLavrov I emailed Professor West, but unfortunately, he said that he couldn't remember where he had seen the statement. So maybe you are right. $\endgroup$
    – licheng
    Sep 21 at 8:07

1 Answer 1

Reset to default
4
$\begingroup$

As mentioned in the comments, it seems unlikely that Troy Barcume's result, whatever it was, is published anywhere.

On the other hand, we have the paper The Complete Catalog of 3-Regular, Diameter-3 Planar Graphs by Robert Pratt, which solves the problem by an exhaustive search. The search space is finite by the Moore bound: in any $3$-regular graph with diameter $3$, there are at most $1 + 3 + 3\cdot 2 + 3 \cdot 2^2 = 22$ vertices. Moreover, the Hoffman and Singleton paper On Moore Graphs with Diameters 2 and 3 shows that for regular graphs with diameter $2$ and $3$, only finitely many cases achieve the moore bound, and this is not one of them; therefore the maximum number of vertices is $20$.

It has been a while since 1996; we have much faster computers, and software like plantri. So I decided to see if we could make the exhaustive search easier to replicate.

Let's begin by showing that any large $3$-regular planar graph with diameter $3$ is $3$-edge-connected. (Or, equivalently, $3$-vertex connected; edge and vertex connectivity are equal for $3$-regular graphs.)

Suppose not: let $G$ be $3$-regular with diameter $3$, and suppose there is some set $X \subseteq E(G)$, with $|X| \le 2$, such that $G-X$ has two components, $G_1$ and $G_2$. If either $G_1$ or $G_2$ had only $1$ or $2$ vertices, they would not be able to get enough edges for $G$ to be $3$-regular. So each has at least $3$ vertices, which means that each one has a vertex not incident on an edge in $X$. Let $v_1 \in V(G_1)$ and $v_2 \in V(G_2)$ be two such vertices. Since the diameter of $G$ is $3$, there must be a $v_1 - v_2$ path of length $3$ or less. The edge from $X$ on that path must be the middle edge, which means that both $v_1$ and $v_2$ must be adjacent to an endpoint of an edge in $X$. With this constraint, there can only be at most $4$ such vertices in each of $G_1$ or $G_2$; together with the endpoints of edges in $X$ (also at most $4$) there can be at most $12$ vertices in $G$. (Moreover, either all vertices in $G_1$ are adjacent to endpoints of both edges in $X$, or else all vertices in $G_2$ are; this rules out $12$ vertices, too.)

Why do we want $3$-connectivity? Because now the dual of $G$ is, first of all, uniquely defined; second, it is a planar triangulation. If $G$ has at most $20$ vertices, then it has at most $30$ edges, so its dual has at most $12$ vertices.

Here is some Mathematica code that runs plantri (well, assuming you separately have plantri) to search the $12$-vertex planar triangulations to see if any of their duals have diameter $3$:

plantri = StartProcess[{"C:/graphtools/plantri", "12", "-d", "-g"}];
Timing[Length[output = Reap[
  While[(line = ReadLine[plantri]) =!= EndOfFile, 
  Sow[ImportString[line, "Graph6"]]]][[2, 1]]]]
Tally[GraphDiameter /@ output]

This outputs two things. First, something like {42.9375, 7595}, which says that in less than 43 seconds, plantri found $7595$ triangulations on $12$ vertices. Second, {{6, 4313}, {5, 3210}, {7, 72}}, which says that the diameters of their duals range from $5$ to $7$, and certainly none of them have diameter $3$.

We can repeat this with $12$ replaced by $11$, $10$, $9$, and finally $8$ (an $8$-vertex planar triangulation has $18$ edges, so its dual is a $12$-vertex $3$-regular graph). It is not until the very end that we see any graphs with diameter $3$, and then Select[output, GraphDiameter[#] == 3 &] produces

the two graphs we wanted to find.

$\endgroup$
7
  • 1
    $\begingroup$ (+1) Glad to see you got the same results. $\endgroup$
    – RobPratt
    Sep 24 at 0:18
  • $\begingroup$ @Misha Lavrov Thank you. But I don't understand this sentence “ each one has a vertex not incident on an edge in $X$” in your proof (incident on an edge in $X$?) . Could you please provide a more detailed explanation? $\endgroup$
    – licheng
    Sep 24 at 7:47
  • $\begingroup$ See my new edits. I provided an example to illustrate my confusion. (Forgive me, I'm not very proficient at inserting images in comments.) $\endgroup$
    – licheng
    Sep 24 at 11:26
  • $\begingroup$ If the edges in $X$ are $\{2,3\}$ and $\{7,8\}$, then vertices $2,3,7,8$ are incident on an edge in $X$, but vertices $1, 4, 5, 6$ are not. $\endgroup$
    – Misha Lavrov
    Sep 24 at 14:39
  • $\begingroup$ Now I understand, I didn’t understand the meaning of “incident on” before. The answer is nice. Another interesting thing, if we don't use computer enumeration, is there any way we can do it? $\endgroup$
    – licheng
    Sep 25 at 0:53

You must log in to answer this question.

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