The (Degree, Diameter) Problem for Planar Graphs

We consider only the special case when the graph is planar. If the graph is also regular, Euler's formula implies that the maximum degree (degree) Δ can be at most 5. Each entry in the first table is either a single number or a closed interval [lower bound, upper bound] containing the order (number of vertices) of the largest planar Δ-regular graph with diameter D. In all cases, the lower bound arises from the construction of a graph. If an entry consists of a single number, the lower and upper bounds are known to be the same. 


LOWER AND UPPER BOUNDS FOR LARGEST PLANAR REGULAR (Δ, D)-GRAPHS (30th October, 2005)
Δ \ D 
1
2
3
4
5
6
7
8
1
2
none exists 
none exists 
none exists 
none exists 
none exists 
none exists 
none exists 
2
3
5
7
9
11
13
15
17
3
4
6
12
[18, 30] 
[28, 62] 
[36, 122] 
[52, 244] 
[76, 488] 
4
none exists
9
[16, 33] 
[27, 96] 
[44, 291] 
[81, 867] 
[134, 2595] 
[243, 7779] 
5
none exists
none exists 
16 
[28, 248] 
[62, 984] 
[124, 3928] 
[254, 11294] 
[500, 62808] 
 

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.


BOUNDS FOR LARGEST PLANAR GRAPHS WITH MAXIMUM DEGREE Δ AND DIAMETER D (2011)
Δ \ D 
2
3
4
5
6
3
7
[12,15]
[18,31]
[28,63]
38
4
9
[16,35]
[27,104]
[44,313]
81
5
10
[19,52]
[39,248]
[73,984]
158
6
11
[24,60]
[52,521]
[114,2409]
280
7
12
[28,68]
[71,938]
[161,3267]
452
8
13
[33,76]
[93,1529]
[225,4257]
685
9
14
[37,84]
[118,2324]
[289,5379]
946
10
16
[42,92]
[146,3353]
[372,6633]
1366
The General (Degree, Diameter) Problem for 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.

hits counter