|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
To confirm the first two rows and extend them infinitely to the right, note that K2 is the only connected (equivalently, finite diameter) 1-regular graph and that cycles are the only connected 2-regular graphs.
To check that the first column is correct, note that the diameter-1 graphs are exactly the complete graphs (by definition) and that both K5 and K6 are nonplanar.
The proof that the 16 vertex 5-regular 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), 133-153. 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 4-regular planar graphs with diameter 4 and 27 vertices. Additionally, using plantri it has been established that there exist no 4-regular planar graphs with 28 vertices and similarly there are no 3-regular planar graphs with diameter 4 with between 20 and 30 vertices.
Most of the previously best-known lower bounds and a proof of the non-existence 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*3D/2-1-2. Also, the lower bound for (4,D), D odd and ≥ 5, should be 4*3(D-1)/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 best-known 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) 349-358.
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: 157-159 (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.