The Degree Diameter Problem for Planar Graphs
From Combinatorics Wiki
Contents
Citation
If you are using combinatoricsWiki, then we would like to ask you to cite the site as follows.
- E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). Combinatorics Wiki, http://combinatoricswiki.org.
If you are using a specific page in combinatoricsWiki, say the "The degree-diameter problem for planar graphs" page, then it would be better to cite the page as follows.
- E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). The degree-diameter problem for planar graphs, Combinatorics Wiki, http://combinatoricswiki.org.
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.