http://combinatoricswiki.org/index.php?action=history&feed=atom&title=The_Degree_Diameter_Problem_for_Toroidal_Graphs
The Degree Diameter Problem for Toroidal Graphs - Revision history
2026-05-21T22:36:57Z
Revision history for this page on the wiki
MediaWiki 1.31.1
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Toroidal_Graphs&diff=311&oldid=prev
Grahame: 1 revision imported
2019-01-03T14:39:33Z
<p>1 revision imported</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en-GB">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 14:39, 3 January 2019</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en-GB"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>
Grahame
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Toroidal_Graphs&diff=310&oldid=prev
CW>Gpineda: /* Table of the orders of the largest known regular toroidal graphs for the undirected degree diameter problem */
2013-06-07T14:27:38Z
<p><span dir="auto"><span class="autocomment">Table of the orders of the largest known regular toroidal graphs for the undirected degree diameter problem</span></span></p>
<p><b>New page</b></p><div>==Table of the orders of the largest known regular toroidal graphs for the undirected degree diameter problem==<br />
<br />
<center> <br />
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"<br />
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8'''<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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'''<br />
|-<br />
|}<br />
</center><br />
<br />
Optimal graphs are marked in bold. The following table is the key to the colors in the table presented above:<br />
<br />
<center><br />
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"<br />
|'''Color''' || style="text-align: center;" |'''Details'''<br />
|-<br />
|style="background-color: red; text-align: center;" | * || The Petersen graph.<br />
|-<br />
|style="background-color: yellow; text-align: center;" | * || Graphs found by Preen. Details are available in a paper by the author.<br />
|-<br />
|style="background-color: green; text-align: center;" | * || Regular planar graphs.<br />
|}<br />
</center><br />
<br />
==Table of the orders of the largest known toroidal graphs for the undirected degree diameter problem==<br />
<br />
<center> <br />
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"<br />
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10''' <br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
|}<br />
</center><br />
<br />
The following table is the key to the colors in the table presented above:<br />
<br />
<center><br />
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"<br />
|'''Color''' || style="text-align: center;" |'''Details'''<br />
|-<br />
|style="background-color: yellow; text-align: center;" | * || Regular toroidal graphs.<br />
|-<br />
|style="background-color: green; text-align: center;" | * || Planar graphs.<br />
|-<br />
|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. <br />
|}<br />
</center><br />
<br />
==References==<br />
<br />
* Feria-Purón, R.; Pineda-Villavicencio, G. (2013), "Constructions of large graphs on surfaces", preprint, [http://arxiv.org/pdf/1302.1648v1.pdf PDF version]. <br />
<br />
* Preen, J. (2010), "Largest 6-regular toroidal graphs for a given diameter", The Australasian Journal of Combinatorics 47:53-57.<br />
<br />
* Tishchenko, S. A. (2001), "The largest graphs of diameter 2 and fixed Euler characteristics", Fundam. Prikl. Mat., 7:1203-1225.<br />
<br />
==External links==<br />
<br />
*[http://faculty.cbu.ca/jpreen/torvaldiam.html Table of the largest known regular toroidal graphs maintained by James Preen]<br />
<br />
<br />
<br />
<br />
<br />
[[Category:The Degree/Diameter Problem]]</div>
CW>Gpineda