The Degree Diameter Problem for Planar Graphs
From Combinatorics Wiki
Revision as of 14:43, 7 June 2013 by CW>Gpineda (→Table of the orders of the largest known regular planar graphs for the undirected degree diameter problem)
Contents
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.