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)
Δ \ D 
1
2
3
4
5
6
7
8
2
3
5
7
9
11
13
15
17
3
4
10 
16 
26 
38 
56 
74 
92 
4
5
13
25 
41 
61 
85 
134 
243 
5
6
16  
30 
48 
70 
124 
254 
500 
6
7  
19  
37  
61 
91 
127 
169 
217 
  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

Return to Planar Table

Return to Home Page

hits counter