The Degree Diameter Problem for Toroidal Graphs

From Combinatorics Wiki

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

d\k 2 3 4 5 6 7 8
3 10 16 26 38 56 74 92
4 13 25 41 61 85 134 243
5 16 30 48 70 124 254 500
6 19 37 61 91 127 169 217

Optimal graphs are marked in bold. The following table is the key to the colors in the table presented above:

Color Details
* The Petersen graph.
* Graphs found by Preen. Details are available in a paper by the author.
* Regular planar graphs.

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

d\k 2 3 4 5 6 7 8 9 10
3 10 16 26 38 56 74 92 120 160
4 13 25 41 61 90 180 270 540 810
5 16 30 48 100 160 400 640 1600 2560
6 19 37 61 150 280 750 1405 3750 7030
7 12 35 74 210 452 1260 2720 7560 16328
8 13 40 97 280 685 1960 4901 13720 33613
9 14 45 122 364 986 2884 7898 23044 63194
10 16 50 151 476 1366 4256 12301 38276 110716

The following table is the key to the colors in the table presented above:

Color Details
* Regular toroidal graphs.
* Planar graphs.
* Graphs found by R. Feria-Purón and G. Pineda-Villavicencio. Details are available in a paper by the authors.

References

  • Feria-Purón, R.; Pineda-Villavicencio, G. (2013), "Constructions of large graphs on surfaces", preprint, PDF version.
  • Preen, J. (2010), "Largest 6-regular toroidal graphs for a given diameter", The Australasian Journal of Combinatorics 47:53-57.
  • Tishchenko, S. A. (2001), "The largest graphs of diameter 2 and fixed Euler characteristics", Fundam. Prikl. Mat., 7:1203-1225.

External links