The Degree Diameter Problem for Toroidal Graphs

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

[math]d[/math]\[math]k[/math]	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

[math]d[/math]\[math]k[/math]	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

• Table of the largest known regular toroidal graphs maintained by James Preen