The (Valency, Diameter) Problem for Toroidal Graphs
In the planar case there are some gaps where some graphs with certain
valencies or diameters cannot exist. One way to address this problem
is to study the largest regular graphs of a given diameter
embedded on the torus. The planar graphs are all still embeddable, but
now we can additionally include
the Petersen graph,
complete graphs up to K7
and the 5-regular graphs of diameter 2.
Each entry in the table is a number
indicating the order (number of vertices) of the largest toroidal
Δ-regular
graph with diameter D.
LOWER BOUNDS FOR LARGEST TOROIDAL REGULAR (Δ,
D)-GRAPHS (December 2009)
The larger bounds in this table are from the planar cases.
The 6-regular graphs are proven to be of maximal order in a paper which has
been accepted for publication in the Australasian Journal of Combinatorics by James Preen.
The diameter 2 cases are given as maximal in S. A. Tishchenko, “The
largest graphs of diameter 2 and fixed Euler characteristics”, Fundam.
Prikl. Mat., 7:4 (2001), 1203 - 1225
Please send any updates or corrections to james_preen at capebretonu.ca