Largest Known (Degree, Diameter)-Graphs (Description)

Largest Known (Degree, Diameter)-Graphs

Diameter 7

Last modification: June 22, 2025.

http://www-mat.upc.es/grup_de_grafs/desc_g7.html

raw adjacency list format: the first vertex of each row is adjacent to all the other vertices in that row.

implicit adjacency list format: each row corresponds to a vertex (row 1, vertex 0; row 2, vertex 1; and so on) and contains all vertices adjacent to it.

adjacency list NX NetworkX format. NetworkX format.

Exoo_196

Delta= 3, Diam= 7; N=196; Moore bound=382;

Download the implicit adjacency list of the graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..). This is the online version

Loz_1320

Degree= 4, Diameter = 7; Order =1320; Moore bound=4373.

Download the raw adjacency list of the graph.

Loz_5516

Degree= 5, Diameter = 7; Order =5 516; Moore bound=27 306.

Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)

Download the raw adjacency list of the graph.

Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz ) Communicated July 2006.

Loz_19383

Degree= 6, Diameter = 7; Order =19383; Moore bound= 117186

Voltage graph Z_21 x(48) Z_923, B(0,3), voltages [(19,865)(7,330)(11,97)], avg. dist.: 5.979465

Z_m x(a) Z_n represents a semidirect product of cyclic groups [x,y][u,v]= [x + u mod m, y*a^u + v mod n].

Download the adjlist NX version of the graph. Link to Eyal Loz's original data. Communicated July 2006.

Found also from other semidirect products (F.Comellas 2024):

Z_21 x(250) Z_923 with generators [2,620 ]<>[19,324 ]:[11,486 ]<>[10,401 ]:[7,279 ]<>[14,76 ]. Avg.dist.: 5.979465 (1,6,30,150,734,3386,10020,5056) transm.: 115894 adjlist NX

Z_21 x(529) Z_923 with generators [13,81 ]:[14,353 ]<>[7,73 ]:[19,422 ]<>[2,333 ]. Avg.dist.: 5.979465 (1,6,30,150,734,3386,10020,5056) transm.: 115894 adjlist NX

Com_53020

Degree= 7, Diameter = 7; Order =53020; Moore bound= 391909

Cayley graph. Found as a semidirect product, 53020 nodes and 185570 edges (F.Comellas 2024):

Z_20 x(729) Z_2651, generators [6,894 ]<>[14,1583 ]:[17,2271 ]<>[3,140 ]:[18,2411 ]<>[2,928 ]:[10,1210 ]<>[10,1210 ]. Avg. dist.: 6.033799 (1,7,42,252,1500,8326,28815,14077) transm.: 319906. adjlist NX
Z_20 x(970) Z_2651, generators [1,533]<>[19,2522]:[18,2238]<>[2,167]:[3,1599]<>[17,170]:[10,1661]<>[10,1661]. Avg. dist.: 6.025896 (1,7,42,252,1510,8414,29028,13766) transm.: 319487. adjlist NX

Former result, Order = 52768

Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)

Voltage graph Z_32 x(19) Z_1649, B(1,3), voltages [31,96 ]:[24,586]:[21,1521]:[16,1088], avg. dist.: 6.038661 (1,7,42,252,1504,8357,28241,14364) transm.: 318642

Z_m x(a) Z_n represents a semidirect product of cyclic groups [x,y][u,v]= [x + u mod m, y*a^u + v mod n].

::: Link to Eyal Loz's original data.

Results for diameter 7 and degrees 8 to 15 (except degree 14) obtained by Eyal Loz and Jozef Širáň. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2006), 63–80.

K₁Σ₈ H₁₁

Delta= 14, Diam= 7; N=6200460; Moore bound= 73206603 ;

J. Gómez, M.A. Fiol and O. Serra, On large (Δ, D) graphs, Discrete Mathematics, 114 (1993), pp. 235. link to the paper

K₁Σ₈ H₁₃

Delta= 16, Diam= 7; N=14882658; Moore bound= 195267857 ;

J. Gómez, M.A. Fiol and O. Serra, On large (Δ, D) graphs, Discrete Mathematics, 114 (1993), pp. 235. link to the paper