View source for The Degree Diameter Problem for Toroidal Graphs

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

<center> 
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
| '''<math>d</math>\<math>k</math>'''||  '''2''' ||  '''3''' ||  '''4'''|| '''5''' ||  '''6''' || '''7''' ||  '''8'''
|-
| '''3''' || style="background-color: red; text-align: center;" |'''10''' || style="background-color: yellow; text-align: center;" |16 ||style="background-color: yellow; text-align: center;" | 26 || style="background-color: yellow; text-align: center;" |38 ||style="background-color: yellow; text-align: center;" | 56 || style="background-color: yellow; text-align: center;" |74 ||style="background-color: yellow; text-align: center;" | 92
|-
| '''4''' ||style="background-color: yellow; text-align: center;" | 13 || style="background-color: yellow; text-align: center;" |25 || style="background-color: yellow; text-align: center;" |41 || style="background-color: yellow; text-align: center;" |61 ||style="background-color: yellow; text-align: center;" | 85 || style="background-color: green; text-align: center;" |134 ||style="background-color: green; text-align: center;" | 243
|-
| '''5''' ||style="background-color: yellow; text-align: center;" | 16 ||style="background-color: yellow; text-align: center;" | 30 || style="background-color: yellow; text-align: center;" |48 || style="background-color: yellow; text-align: center;" |70 || style="background-color: green; text-align: center;" |124 ||style="background-color: green; text-align: center;" | 254 ||style="background-color: green; text-align: center;" | 500
|-
| '''6''' ||style="background-color: yellow; text-align: center;" | '''19''' ||style="background-color: yellow; text-align: center;" | '''37''' || style="background-color: yellow; text-align: center;" |'''61''' || style="background-color: yellow; text-align: center;" |'''91''' || style="background-color: yellow; text-align: center;" |'''127''' ||style="background-color: yellow; text-align: center;" | '''169''' ||style="background-color: yellow; text-align: center;" | '''217'''
|-
|}
</center>

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

<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: red; text-align: center;" | * || The Petersen graph.
|-
|style="background-color: yellow; text-align: center;" | * || Graphs found by Preen. Details are available in a paper by the author.
|-
|style="background-color: green; text-align: center;" | * || Regular planar graphs.
|}
</center>

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

<center> 
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
| '''<math>d</math>\<math>k</math>'''||  '''2''' ||  '''3''' ||  '''4'''|| '''5''' ||  '''6''' ||  '''7''' ||  '''8''' ||  '''9''' ||  '''10''' 
|-
| '''3''' || style="background-color: yellow; text-align: center;" | '''10''' || style="background-color: yellow; text-align: center;" | 16 || style="background-color: yellow; text-align: center;" | 26 || style="background-color: yellow; text-align: center;" | 38 || style="background-color: yellow; text-align: center;" | 56||style="background-color: yellow; text-align: center;" | 74||style="background-color: yellow; text-align: center;" | 92||style="background-color: #00ff7f; text-align: center;" |120||style="background-color: #00ff7f; text-align: center;" |160
|-
| '''4''' || style="background-color: yellow; text-align: center;" | 13 || style="background-color: yellow; text-align: center;" | 25 || style="background-color: yellow; text-align: center;" | 41 || style="background-color: yellow; text-align: center;" | 61 || style="background-color: #00ff7f; text-align: center;" | 90||style="background-color: #00ff7f; text-align: center;" |180||style="background-color: #00ff7f; text-align: center;" | 270||style="background-color: #00ff7f; text-align: center;" |540||style="background-color: #00ff7f; text-align: center;" |810
|-
| '''5''' || style="background-color: yellow; text-align: center;" | 16 || style="background-color: yellow; text-align: center;" | 30 || style="background-color: yellow; text-align: center;" | 48 || style="background-color: #00ff7f; text-align: center;" | 100 || style="background-color:#00ff7f; text-align: center;" | 160||style="background-color: #00ff7f; text-align: center;" |400||style="background-color: #00ff7f; text-align: center;" |640||style="background-color: #00ff7f; text-align: center;" |1600||style="background-color:#00ff7f; text-align: center;" |2560
|-
| '''6''' || style="background-color: yellow; text-align: center;" | 19 || style="background-color: yellow; text-align: center;" | 37 || style="background-color:yellow; text-align: center;" | 61 || style="background-color: #00ff7f; text-align: center;" | 150 || style="background-color: green; text-align: center;" | 280||style="background-color: #00ff7f; text-align: center;" |750||style="background-color:green; text-align: center;" |1405||style="background-color: #00ff7f; text-align: center;" |3750||style="background-color:green; text-align: center;" |7030
|-
| '''7''' || style="background-color: green; text-align: center;" | 12 || style="background-color: #00ff7f; text-align: center;" | 35||  style="background-color:green; text-align: center;"  | 74 || style="background-color: #00ff7f; text-align: center;" | 210|| style="background-color: green; text-align: center;" | 452||style="background-color: #00ff7f; text-align: center;" | 1260||style="background-color:green; text-align: center;" |2720||style="background-color: #00ff7f; text-align: center;" |7560||style="background-color:green; text-align: center;" |16328
|-
| '''8''' || style="background-color: green; text-align: center;" | 13 || style="background-color: #00ff7f; text-align: center;" | 40 ||  style="background-color:green; text-align: center;"  | 97 || style="background-color: #00ff7f; text-align: center;" | 280 || style="background-color: green; text-align: center;" |685||style="background-color: #00ff7f; text-align: center;" | 1960||style="background-color:green; text-align: center;" |4901||style="background-color: #00ff7f; text-align: center;" |13720||style="background-color:green; text-align: center;" |33613
|-
| '''9''' || style="background-color: green; text-align: center;" | 14 || style="background-color: #00ff7f; text-align: center;" | 45 || style="background-color:green; text-align: center;"  | 122 || style="background-color: #00ff7f; text-align: center;" | 364 || style="background-color: green; text-align: center;" |986||style="background-color: #00ff7f; text-align: center;" | 2884||style="background-color:green; text-align: center;" |7898||style="background-color: #00ff7f; text-align: center;" |23044||style="background-color:green; text-align: center;" |63194
|-
| '''10''' || style="background-color: green; text-align: center;" | 16 || style="background-color: #00ff7f; text-align: center;" | 50 || style="background-color: green; text-align: center;" | 151 || style="background-color: #00ff7f; text-align: center;" | 476 || style="background-color: green; text-align: center;" | 1366||style="background-color: #00ff7f; text-align: center;" | 4256 ||style="background-color:green; text-align: center;" |12301||style="background-color: #00ff7f; text-align: center;" |38276||style="background-color:green; text-align: center;" |110716
|-
|}
</center>

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

<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: yellow; text-align: center;" | * || Regular toroidal graphs.
|-
|style="background-color: green; text-align: center;" | * || Planar graphs.
|-
|style="background-color: #00ff7f; text-align: center;" | * || Graphs found by R. Feria-Purón and G. Pineda-Villavicencio. Details are available in a paper by the authors. 
|}
</center>

==References==

* Feria-Purón, R.; Pineda-Villavicencio, G. (2013), "Constructions of large graphs on surfaces", preprint, [http://arxiv.org/pdf/1302.1648v1.pdf 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==

*[http://faculty.cbu.ca/jpreen/torvaldiam.html Table of the largest known regular toroidal graphs maintained by James Preen]





[[Category:The Degree/Diameter Problem]]