Largest Known (Degree, Diameter)-Graphs
Diameter 4
Last modification: July 30, 2006.
http://www-mat.upc.es/grup_de_grafs/desc_g.html
vC, AFY
Delta= 3, Diam= 4; N=38; Moore bound=46;
optimal
Described independently in:
- von Conta, C; Torus and other networks as communication
networks with up to some hundred points;
IEEE Trans Comp,c-32 (1983), pp. 657-666.
- Alegre, I.; Fiol, M.A. and Yebra, J.L.A;
Some large graphs with given degree and diameter;
J. Graph Theory,10 (1986), pp.219-224.
The proof of optimality appeared in:
Dominique Buset;
Maximal cubic graphs with diameter 4; Discrete Math.,101 (2000), pp. 53--61.
96
Delta= 4, Diam= 4; N=96; Moore bound=161;
Exoo_96
Download the Cabri text file of the graph.
Download the adjacency list of the graph.
S_210
Delta= 5, Diam= 4; N=210; Moore bound=426;
Obtained as a Cayley graph for semidirect product of Zm with Zn
Group Generators Inverses Order of Generator
12*(67)105 10,17 2,22 8,58 4,62 6,0
Loz_390
Degree= 6, Diameter = 4; Order =390; Moore
bound=937
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Download the adjacency list of the graph.
Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz )
Communicated July 2006.
S_672
Degree= 7, Diameter = 4; Order =672; Moore bound=1814
Obtained as a Cayley graph for semidirect product of Zm with Zn
6*(39) 112 2,73 4,23 5,54 1,22 5,71 1,31 3,42
M. Sampels. In: Rolf H. Möhring (Ed.): 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '97), Lecture Notes in Computer Science 1335, pp. 288-302, Springer-Verlag, 1997
ISBN 3-540-63757-5
Loz_1100
Degree= 8, Diameter = 4; Order =1100;
Moore bound=3201
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Download the adjacency list of the graph.
Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz )
Communicated July 2006.
Loz_1550
Degree= 9, Diameter = 4; Order =1550;
Moore bound=5266.
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Download the adjacency list of the graph.
Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz )
Communicated July 2006.
Loz_2223
Degree= 10, Diameter = 4; Order =2223;
Moore bound=8201.
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Download the adjacency list of the graph.
Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz )
Communicated July 2006.