





















































To confirm the first two rows and extend them infinitely to the right, note that K_{2} is the only connected (equivalently, finite diameter) 1regular graph and that cycles are the only connected 2regular graphs.
To check that the first column is correct, note that the diameter1 graphs are exactly the complete graphs (by definition) and that both K_{5} and K_{6} are nonplanar.
The proof that the 16 vertex 5regular graph is indeed the largest one of diameter 3 was completed by James Preen in June 2005 and is awaiting publication.
The upper bound for (5,7) comes from the following paper:
M. Fellows, P. Hell, and K. Seyffarth. Large planar graphs with given diameter and maximum degree. Disc. Appl. Math. 61 (1995), 133153. MR 96e:05081.
The lower bound for (5,4) comes from a set of 54 graphs (the one illustrated has radius 3) constructed by James Preen, who also constructed the (4,4) graph which has now been proven to be one of six 4regular planar graphs with diameter 4 and 27 vertices. Additionally, using plantri it has been established that there exist no 4regular planar graphs with 28 vertices and similarly there are no 3regular planar graphs with diameter 4 with between 20 and 30 vertices.
Most of the previously bestknown lower bounds and a proof of the nonexistence of (5,2) can be found in the following paper:
F. Göbel and W. Kern. Planar regular graphs with prescribed diameter. Univ. of Twente (The Netherlands) Applied Math. Memorandum No. 1183, December 1993.
The lower bounds for (3,D), D ≥ 6; (4,D), D ≥ 5; and (5,D), D ≥ 5 arose from Pratt and Friedman improving the constructions of Göbel and Kern.
The lower bound for (4,D), D even and ≥ 4, given without proof in Proposition 3.2(c) in the Göbel/Kern paper, should be 8*3^{D/21}2. Also, the lower bound for (4,D), D odd and ≥ 5, should be 4*3^{(D1)/2}2. These corrections have been verified by Frits Göbel, but Erich Friedman and Rob Pratt have improved the bounds, as reflected in this table:
The second table gives the bestknown bounds for the number of vertices in a planar (but not necessarily regular) graph with maximum degree Δ and diameter D. Almost all of these bounds are due to Fellows, Hell, and Seyffarth. The proof of the exactitude of (4,2) to (7,2) is from "Largest planar graphs and largest maximal planar graphs of diameter two." (Yang, Yuansheng, Lin, Jianhua, Dai, Yongjie) J. Comput. Appl. Math. 144 (2002) 349358.
The lower bounds for (3,6) and (5,4) come from graphs constructed by Geoff Exoo using simulated annealing and tabu search. The optimality of those of diameter 6 (and all other even diameters larger) was shown by S. A. Tishchenko in ``Maximum size of a planar graph with given degree and diameter'', Electronic Notes in Discrete Mathematics 31: 157159 (2008). Note that the lower bounds for Δ = 4 currently agree with those for regular graphs.






















































Please send any updates or corrections to james_preen at capebretonu.ca
Page originally compiled by Rob Pratt and rescued from the internet archive in 2005.