Table of the orders of the largest known regular planar graphs for the undirected degree diameter problem
| [math]d[/math]\[math]k[/math] |
2 |
3 |
4 |
5 |
6 |
7 |
8
|
| 3 |
6 |
12 |
18 |
28 |
36 |
52 |
76
|
| 4 |
9 |
16 |
27 |
44 |
81 |
134 |
243
|
| 5 |
NA |
16 |
28 |
62 |
124 |
254 |
500
|
Optimal graphs are marked in bold. The following table is the key to the colors in the table presented above:
| Color |
Details
|
| * |
Graphs found by Preen.
|
| * |
Graphs found by Pratt and Friedman.
|
Table of the orders of the largest known planar graphs for the undirected degree diameter problem
| [math]d[/math]\[math]k[/math] |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10
|
| 3 |
7 |
12 |
18 |
28 |
38 |
53 |
77 |
109 |
157
|
| 4 |
9 |
16 |
27 |
44 |
81 |
134 |
243 |
404 |
728
|
| 5 |
10 |
19 |
39 |
73 |
158 |
289 |
638 |
1153 |
2558
|
| 6 |
11 |
24 |
55 |
117 |
280 |
579 |
1405 |
2889 |
7030
|
| 7 |
12 |
28 |
74 |
165 |
452 |
984 |
2720 |
5898 |
16328
|
| 8 |
13 |
33 |
97 |
228 |
685 |
1590 |
4901 |
11124 |
33613
|
| 9 |
14 |
37 |
122 |
293 |
986 |
2338 |
7898 |
18698 |
63194
|
| 10 |
16 |
42 |
151 |
375 |
1366 |
3369 |
12301 |
30315 |
110716
|
Optimal graphs are marked in bold. The following table is the key to the colors in the table presented above:
| Color |
Details
|
| * |
Graphs of unknown author.
|
| * |
Graphs found by Fellows, Hell, and Seyffarth. Details are available in a paper by the authors.
|
| * |
Graphs found by Yang, Lin, and Dai. Details are available in a paper by the authors.
|
| * |
Graphs found by Geoffrey Exoo.
|
| * |
Graphs found by S. A. Tishchenko. Details are available in a paper by the author.
|
| * |
Graphs found by R. Feria-Purón and G. Pineda-Villavicencio. Details are available in a paper by the authors.
|
References
- Fellows, M.; Hell, P.; Seyffarth, K. (1998), "Constructions of large planar networks with given degree and diameter", Networks 32: 275-281.
- Feria-Purón, R.; Pineda-Villavicencio, G. (2013), "Constructions of large graphs on surfaces", preprint, PDF version.
- Tishchenko, S. A. (2012), "Maximum size of a planar graph with given degree and even diameter", European Journal of Combinatorics 33: 380-396.
- Yang, Y.; Lin, J.; Dai, Y. (2002), "Largest planar graphs and largest maximal planar graphs of diameter two", Journal of Computational and Applied Mathematics 144:349-358.
External links