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

Largest Known (Degree, Diameter)-Graphs

Diameter 3

last modifications: June 22, 2025, html corrections. April 13, 2025. -- added adjacency lists for entries (9,3), (10,3), (11,3), (12,3), (14,3), (15,3), and (16.3), provided by V. Pelekhaty --

https://web.mat.upc.edu/francesc.comellas/old-files/delta-d/taula_delta_d.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.

C5xF4

Degree= 3, Diam= 3; N=20; Moore bound=22; optimal

B. Elpass. Topological constraints on interconnection-limited logic. 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, NJ, USA, 1964, pp. 133-137. doi:10.1109/SWCT.1964.27

A detailed description: I. Alegre, M.A. Fiol and J.L.A Yebra; Some large graphs with given degree and diameter; J. Graph Theory,10 (1986), pp.219-224. doi:10.1002/jgt.3190100211

Download the NX adjacency list of C5xF4. Download the implicit adjacency list of C5xF4.

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

Allwr

Delta= 4, Diam= 3; N=41; Moore bound=53;

Graphs found by James Allwright (School of Computer Science, University of Westminster) by using a heuristic algorithm.

13 non isomorphic graphs with 41 vertices were found.

J. Allwright, New (Delta, D) graphs discovered by heuristic search. Discrete Applied Mathematics , 37/38 (1992), pp. 3--8.

Adjacency list NX of Graph 1(a).

Adjacency list NX of Graph 1(b). Obtained from 1(a) by the 2-swap [(25,34),(30,33) to (25,33),(30,34)].

Adjacency list NX of Graph 1(c) . Obtained from 1(b) by the 2-swap [(31,6), (32,5) to (31,5), (32,6)].

Adjacency list NX of Graph 1(d) . Obtained from 1(c) by the 2-swap [(17,20), (28,31) to (17,31), (28,20)].

Adjacency list NX of Graph 1(e) . Obtained from 1(d) by the 2-swap [(16,21), (27,32) to (16,32), (27,21)].

Adjacency list NX of Graph 1(f) . Obtained from 1(e) by the 2-swap [(14,33), (19,34) to (14,34), (19,33)].

Adjacency list NX of Graph 2(a) .

Adjacency list NX of Graph 2(b) . Obtained from 2(a) by the 2-swap [(4,35), (7,38) to (4,38), (7,35)].

Adjacency list NX of Graph 2(c) . Obtained from 2(b) by the 2-swap [(16,31), (17,32) to (16,32), (17,31)].

Adjacency list NX of Graph 3 .

Adjacency list NX of Graph 4 .

Adjacency list NX of Graph 5 .

Adjacency list NX of Graph 6 .

Graphs 1(a) to 1(f) all share the same average distance of 2.5036585. Graphs 3, 4, 5 and 6 have an average distance of 2.5.

I corrected Graph 4 from the Fig. 3 of Allwright's paper, as it initially produced a graph with a diameter of 4. If we label the vertices of Graph 4 from Fig. 3 of the paper from left to right and top to bottom (starting with 1), we need to swap the edges (12, 32) and (13, 37) to obtain the intended graph, which gives the correct values for the diameter and the number of k-cycles in the paper. In the above figure, I have removed the wrong edges and added (in red) the correct ones.

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

Note that a few values computed by this script with respect symmetry group sizes do not match those reported in the paper. I have verified these results with Mathematica and I believe they are correct. Also the value of the number of 9-cycles for Graph 6 is 937 and not 938 as stated in the paper (likely a misprint).

Exoo_72

Delta= 5, Diam= 3; N=72; Moore bound=106;

Communicated by G. Exoo (May 22, 1998). G.E. data

Download the implicit adjacency list of the graph.

Download the adjacency list NX of the graph.

Geoffrey Exoo. A family of graphs and the degree/diameter problem. J. Graph Theory 37 (2001), 118-124.

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

Exoo_111

Delta= 6, Diam= 3; N=111; Moore bound=187;

Communicated by G. Exoo (May 19, 2010). G.E. data

Download the implicit adjacency list of the graph.

Download the adjacency list NX of the graph.

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

Exoo_168

Delta= 7, Diam= 3; N=168; Moore bound=302;

Communicated by G. Exoo (November 1, 2005). G.E. data

Download the implicit adjacency list of the graph.

Download the adjacency list NX of the graph.

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

CM_253

Degree= 8, Diameter = 3; Order =253; Moore bound=457.

Obtained (08/1994) by F. Comellas, M. Mitjana as a Cayley graph for a semidirect product.

Z_11*(9)Z_23 -- [7,2]<>[4,11]; [10,4]<>[1,10]; [1,16]<>[10,11]; [9,17]<>[2,3]

Dist. Distrib. 1,8,52,192, avg. dist.: 2.730159 (implicit adjacency list ) --- adjlist NX

Other instances found (F.Comellas 2024) -all are isomorphic to the former-

Z_11*(2)Z_23 -- [5,14]<>[6,1]; [5,11]<>[6,9]; [2,9]<>[9,15]; [10,4]<>[1,15] Avg. dist. 2.730159 adjlist NX

Z_11*(3)Z_23 -- [9,1]<>[2,14]; [4,1]<>[7,21]; [3,12]<>[8,20]; [2,4]<>[9,20] Avg. dist. 2.730159 adjlist NX

Z_11*(4)Z_23 -- [8,9]<>[3,22]; [10,0]<>[1,0]; [5,10]<>[6,3]; [8,14]<>[3,1] Avg. dist. 2.730159 adjlist NX

Z_11*(6)Z_23 -- [1,17]<>[10,1]; [6,5]<>[5,13]; [8,4]<>[3.10]; [3,3]<>[8,15] Avg. dist. 2.730159 adjlist NX

Z_11*(8)Z_23 -- [2,6]<>[9,15]; [2,17]<>[9,8]; [7,14]<>[4,18]; [3,0]<>[8,0] Avg. dist. 2.730159 adjlist NX

Z_11*(12)Z_23 -- [2,0]<>[9,0]; [1,8]<>[10,7]; [5,13]<>[6,21]; [6,2]<>[5,10] Avg. dist. 2.730159 adjlist NX

Z_11*(13)Z_23 -- [4,3]<>[7,19]; [3,3]<>[8,17]; [5,17]<>[6,13]; [7,18]<>[4,21] Avg. dist. 2.730159 adjlist NX

Z_11*(16)Z_23 -- [7,5]<>[4,1]; [3,21]<>[8,1]; [4,3]<>[7,15]; [6,18]<>[5,7] Avg. dist. 2.730159 adjlist NX

Z_11*(18)Z_23 -- [2,16]<>[9,15]; [10,19]<>[1,3]; [10,17]<>[1,16]; [4,1]<>[7,17] Avg. dist. 2.730159 adjlist NX

--------------------

253deg8D3-FC.zip is a zip file containing the programs used to obtain the results for this graph and for the graphs (3,5), (6,8), (7,6), (7,7), (8,5), (9,4), (10,4), (10,5), (11,5), (12,5), (13,5), (14,5), and (15,5), which were found by the author in 2024. The C program included is the same one that computed this particular (8,3) entry in 1994, with only minor modifications to its output format. See entries (3,5)=70 and (3,8)=360 for other versions of these programs.

--------------------

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

--------------------

Also obtained in January 1997 as a Cayley graph for semidirect product of Zm with Zn.

Z_11*(3)Z_23 -- [2,0]<>[9,0]; [2,13]<>[9,19]; [3,1]<>[8,17]; [4,22]<>[7,2]

avg. dist.: 2.730159

M. Sampels. Large networks with small diameter. Proc. 23rd Int. Workshop on Graph Theoretic Concepts in Computer Science (WG'97), LNCS 1335, pp. 288-302. Springer-Verlag, 1997. Communicated July 29, 1997 adjlist NX.

This instance is also isomorphic to the other cases.

Q′₈

Delta= 9, Diam= 3; N=585; Moore bound= 658;

Quotient of the incidence graph of a regular generalized quadrangle by a polarity.

C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

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

Q′₈d

Delta= 10, Diam= 3; N=650; Moore bound= 911;

Quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices.

C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

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

Q′₈d

Delta= 11, Diam= 3; N=715; Moore bound= 1222;

Quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices.

C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

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

Q′₈d+

Delta= 12, Diam= 3; N=786; Moore bound= 1597;

Quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices.

J. Gómez. Some new large (Δ,3) graphs.Networks 53 (2009), pp. 1-5. link

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

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

Q′₈d++

Delta= 13, Diam= 3; N=856; Moore bound=2042;

Obtained by Vladimir Pelekhaty (vpelekhaty at aol.com) "I started with Jose Gomez's Q′₈d+ graph (13,3)=851 --see link -- , and added a few (odd number of) nodes before regularizing it by connecting the dangling degrees". Communicated August 6, 2021.

Download the implicit adjacency list of the graph. adjlist NX

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

Q′₈d+

Delta= 14, Diam= 3; N=916; Moore bound= 2563;

J. Gómez. Some new large (Δ,3) graphs.Networks 53 (2009), pp. 1-5. link

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

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

(⊗ Q_2,4)′

Delta= 15, Diam= 3; N=1215; Moore bound= 3166;

Component with polarity of the cartesian product of the quocient of a quadrangle by a polarity by itself.

C. Delorme. Large bipartite graphs with given degree and diameter. J. Graph Theory, 9 (1985) 325–334.

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

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

(⊗ Q₃)′

Delta= 16, Diam= 3; N=1600; Moore bound= 3857;

Component with polarity of the cartesian product of the quocient of a quadrangle by a polarity by itself.

C. Delorme and G. Farhi. Large graphs with given degree and diameter.IEEE Trans, Comput. c-33 (1984), pp. 857-860. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

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