The Degree Diameter Problem for Planar Graphs

From Combinatorics Wiki

Jump to: navigation, search

Contents

Table of the orders of the largest known regular planar graphs for the undirected degree diameter problem

d\k 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

d\k 2 3 4 5 6 7 8 9 10
3 7 12 18 28 38 53 77109157
4 9 16 27 44 81134 243404728
5 10 19 39 73 15828963811532558
6 11 24 55 117 280579140528897030
7 12 28 74 165 452 9842720589816328
8 13 33 97 228 685 159049011112433613
9 14 37 122 293 986 233878981869863194
10 16 42 151 375 1366 33691230130315110716

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