The Degree/Diameter Problem

From

Introduction

A full description of the degree diameter problem is available from Combinatorics Wiki. Below is a short summary, and tables presenting the graphs I found as part of the PhD work I have done during 2006-2008. Adjacency lists to some of the graphs that I found, of order less than 20,000 are also available.

Undirected graphs

The degree diameter problem is the problem of finding the largest possible number N(d,k) of vertices in a graph of maximum degree d and diameter k.

We call a graph of maximum degree d and diameter k a (d,k)-graph.

An upper bound on the order of a (d,k)-graph is given by the expression (d(d-1)^k-2)(d-2)^-1, known as the Moore bound, and denoted by M(d,k).

Graphs whose order attains the Moore bound are called Moore graphs. Moore graphs are very rare. They are the complete graphs on d+1 vertices, the cycles on 2k+1 vertices, and for diameter 2, the Petersen graph, the Hoffman-Singleton graph and probably a graph of degree d = 57. For 2 < k and 2 < d, there are no Moore graphs.

Consequently, research activities in the degree/diameter problem cover (i) Constructions of ever larger graphs, which provide better lower bounds on N(d,k) and (ii) Proofs of the non-existence or otherwise of graphs whose order misses the Moore bound by a small number of vertices. A comprehensive information source, covering the current state of knowledge in the degree/diameter problem for general graphs can be found here.

Directed graphs

In the context of digraphs the degree/diameter problem can be considered as the problem of finding the largest possible number DN(d,k) of vertices in a digraph of maximum out-degree d and diameter k.

We call a digraph of maximum out-degree d and diameter k a (d,k)-digraph.

An upper bound on the order of a (d,k)-digraph is given by the expression (d^k+1-1)(d-2)^-1, known as the directed Moore bound, and denoted by DM(d,k).

Digraphs attaining the directed Moore bound are called Moore digraphs, and they are even rarer than the Moore graphs. Moore digraphs are the directed cycles on k+1 vertices and the complete digraphs on d+1 vertices. For 1 < k and 1 < d, there are no Moore digraphs. A comprehensive information source, covering the current state of knowledge in the degree/diameter problem for general digraphs can be found here.

The degree/diameter problem for several classes of graphs:

The following set of tables list all the graphs I found as part of my ongoing interest in the degree diameter problem. I am also currently working with Hebert Pérez-Rosés, Guillermo Pineda Villavicencio and Jozef Širáň, on different aspects of the degree diameter problem.

If, in addition to the limits on the degree and the diameter, we add further constraints to the graphs in question, we can state the degree/diameter problem for several classes of graphs, such as bipartite graphs, vertex-transitive graphs, Cayley graphs, arc-transitive graphs, and the corresponding versions for digraphs. In these cases we denote the largest possible number of nodes by N^b(d,k) (for bipartite graphs), N^vt(d,k) (for vertex-transitive graphs), N^c(d,k) (for Cayley graphs), and N^at(d,k) (for arc-transitive graphs), respectively.

For only a few classes of graphs, better general upper bounds are known.

The undirected case:

General graphs:

For complete information on the general undirected case please refer to the degree/diameter problem for general graphs. Below is the table of the largest known graphs (as of January 2009) that I found (with orange background). Graphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal.

d\k	2	3	4	5	6	7	8	9	10
3	10	20	38	70	132	196	336	600	1 250
4	15	41	96	364	740	1 320	3 243	7 575	17 703
5	24	72	210	624	2 772	5 516	17 030	57 840	187 056
6	32	110	390	1 404	7 917	19 383	76 461	307 845	1 253 615
7	50	168	672	2 756	11 988	52 768	249 660	1 223 050	6 007 230
8	57	253	1 100	5 060	39 672	131 137	734 820	4 243 100	24 897 161
9	74	585	1 550	8 200	75 893	279 616	1 686 600	12 123 288	65 866 350
10	91	650	2 286	13 140	134 690	583 083	4 293 452	27 997 191	201 038 922
11	104	715	3 200	19 500	156 864	1 001 268	7 442 328	72 933 102	600 380 000
12	133	786	4 680	29 470	359 772	1 999 500	15 924 326	158 158 875	1 506 252 500
13	162	851	6 560	40 260	531 440	3 322 080	29 927 790	249 155 760	3 077 200 700
14	183	916	8 200	57 837	816 294	6 200 460	55 913 932	600 123 780	7 041 746 081
15	186	1 215	11 712	76 518	1 417 248	8 599 986	90 001 236	1 171 998 164	10 012 349 898
16	198	1 600	14 640	132 496	1 771 560	14 882 658	140 559 416	2 025 125 476	12 951 451 931

Cayley graphs

For complete information on degree diameter Cayley graphs please refer to the degree/diameter problem for Cayley graphs. Below is the table of the largest known graphs (as of January 2009) that I found (with orange background). Graphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal. Note that the graphs with lighter orange background also appear in the table above.

d\k	2	3	4	5	6	7	8	9	10
3	8	14	24	60	72	168	300	506	820
4	13	30	84	205	513	1 155	3 080	7 550	17 604
5	18	60	210	546	1 640	5 500	16 965	57 840	187 056
6	32	108	375	1 395	5 115	19 383	76 461	307 845	1 253 615
7	36	168	672	2 756	11 988	52 768	249 660	1 223 050	6 007 230
8	48	253	1 100	5 060	23 991	131 137	734 820	4 243 100	24 897 161
9	60	294	1 550	8 200	45 612	279 616	1 686 600	12 123 288	65 866 350
10	72	406	2 286	13 140	81 235	583 083	4 293 452	27 997 191	201 038 922
11	84	486	2 860	19 500	139 446	1 001 268	7 442 328	72 933 102	500 605 110
12	96	605	3 775	29 470	229 087	1 999 500	15 924 326	158 158 875	1 225 374 192
13	108	680	4 788	40 260	347 126	3 322 080	29 927 790	233 660 788	2 129 329 324
14	128	873	6 510	57 837	530 448	5 600 532	50 128 239	579 328 377	7 041 746 081
15	144	972	7 956	76 518	787 116	8 599 986	88 256 520	1 005 263 436	10 012 349 898
16	150	1 155	9 576	100 650	1 125 264	12 500 082	135 340 551	1 995 790 371	12 951 451 931
17	162	1 260	12 090	133 144	1 609 830	18 495 162	220 990 700	3 372 648 954
18	171	1 510	15 026	171 828	2 193 321	26 515 120	323 037 476	5 768 971 167
19	200	1 638	17 658	221 676	3 030 544	39 123 116	501 001 000	8 855 580 344
20	203	1 958	21 333	281 820	4 040 218	55 625 185	762 374 779	12 951 451 931

Cayley Graphs of Diameter Two

For the special case of diameter 2, Cayley graphs of degree up to 12 are known to be optimal. It is interesting to note that optimal Cayley graphs are smaller than the Moore bound (as shown in the table below).

Jana Šiagiová and Jozef Širáň have found a general construction for Cayley graphs. SS graphs are constructed using semi-direct products of a product of finite fields and Z₂, where each such group yields a range of graphs of different degrees. SS graphs are the largest known Cayley graphs for degree larger than 30 and diameter 2, with order up to about 50% of the Moore bound.

A range of Cayley graphs of diameter 2 and degree larger than 12 was found by Eyal Loz using semi-direct products of cyclic groups.

<math>d</math>	Order	% Moore Bound
4	13	76.47%
5	18	69.23%
6	32	86.48%
7	36	72%
8	48	73.84%
9	60	73.17%
10	72	71.28%
11	84	68.85%
12	96	66.20%
13	112	65.88%
14	128	64.97%
15	144	63.71%
16	155	60.31%
17	170	58.62%
18	192	59.07%
19	200	55.24%
20	210	52.36%
21	242	54.75%
22	242	49.89%
23	258	48.67%
24	275	47.66%
25	338	53.99%
26	338	49.92%
27	338	46.30%
28	338	43.05%
29	342	40.61%
30	372	41.28%

<math>d</math>	Order	% Moore Bound
31	512	53.22%
32	512	49.95%
33	578	53.02%
34	578	49.95%
35	578	47.14%
36	578	44.56%
37	722	52.70%
38	722	49.96%
39	722	47.43%
40	722	45.09%
41	722	42.92%
42	722	40.90%
43	722	39.02%
44	722	37.27%
45	1058	52.22%
46	1058	49.97%
47	1058	47.87%
48	1058	45.90%
49	1250	52.03%
50	1250	49.98%
51	1250	48.03%
52	1250	46.21%
53	1458	51.88%
54	1458	49.98%
55	1458	48.18%
56	1458	46.47%
57	1682	51.75%

Color	Details
*	Optimal Cayley Graphs found by Marston Conder.
*	Cayley Graphs found by Eyal Loz.
*	Cayley Graphs found by Jana Šiagiová and Jozef Širáň.

Bipartite graphs

For complete information on the bipartite case please refer to the degree/diameter problem for bipartite graphs. Below is the table of the largest known graphs (as of January 2009) that I found (with orange background). Graphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal. Note that some of the graphs in this table also appear in the table above.

d\k	3	4	5	6	7	8	9	10
3	14	30	56	126	168	256	506	800
4	26	80	160	728	840	2 184	4 970	11 748
5	42	170	336	2 730	3 110	9 234	27 936	90 068
6	62	312	684	7 812	8 310	29 790	117 360	452 032
7	80	346	1 134	8 992	23 436	80 940	400 160	1 987 380
8	114	800	1 710	39 216	40 586	201 480	1 091 232	6 927 210
9	146	1 170	2 496	74 898	117 648	449 480	2 961 536	20 017 260
10	182	1 640	4 000	132 860	224 694	1 176 480	7 057 400	50 331 156
11	186	1 734	5 850	142 464	398 580	2 246 940	15 200 448	130 592 354
12	266	2 928	8 200	354 312	664 300	4 650 100	30 001 152	300 383 050
13	270	3 064	11 480	374 452	1 062 936	5 314 680	50 990 610	617 330 936
14	366	4 760	14 760	804 468	1 771 560	14 172 480	95 087 738	1 213 477 190
15	370	4 946	20 496	842 048	2 480 184	XXX	168 016 334	2 300 326 510
16	394	5 134	27 300	884 062	4 022 340	36 201 060	288 939 118	4 119 507 330

The directed case:

For complete information on the general directed case please refer to the degree/diameter problem for general digraphs.

Vertex symmetric digraphs

For complete information on the general directed case please refer to the degree/diameter problem for vertex symmetric digraphs. Below is the table of the largest known vertex symmetric digraphs (as of January 2009) that I found (with orange background). Digraphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal. For some values of d and k the complete list of distinct Cayley digraphs is linked from the table.

d\k	2	3	4	5	6	7	8	9	10	11
2	6	10	20	27	72	144	171	336	504	737
3	12	27	60	165	333	1 152	2 041	5 115	11 568	41 472
4	20	60	168	465	1 378	7 200	14 400	42 309	137 370	648 000
5	30	120	360	1 152	3 775	28 800	86 400	259 200	1 010 658	5 184 000
6	42	210	840	2 520	9 020	88 200	352 800	1 411 200	5 184 000	27 783 000
7	56	336	1 680	6 720	20 160	225 792	1 128 960	5 644 800	27 783 000	113 799 168
8	72	504	3 024	15 120	60 480	508 032	3 048 192	18 289 152	113 799 168	457 228 800
9	90	720	5 040	30 240	151 200	1 036 800	7 257 600	50 803 200	384 072 192	1 828 915 200
10	110	990	7 920	55 400	332 640	1 960 200	15 681 600	125 452 800	1 119 744 000	6 138 320 000
11	132	1 320	11 880	95 040	665 280	3 991 680	31 152 000	282 268 800	2 910 897 000	18 065 203 200
12	156	1 716	17 160	154 440	1 235 520	8 648 640	58 893 120	588 931 200	6 899 904 000	47 703 427 200
13	182	2 184	24 024	240 240	2 162 160	17 297 280	121 080 960	1 154 305 152	15 159 089 098	115 430 515 200

References

Bannai, E.; Ito, T. (1973), "On finite Moore graphs", J. Fac. Sci. Univ. Tokyo Ser. A 20: 191–208, MR0323615
Bridges, W. G.; Toueg, S. (1980), "On the impossibility of directed Moore graphs", Journal of Combinatorial Theory, Series B 29 (3), 339--341, doi:10.1016/0095-8956(80)90091-X.
J. Dinneen, Michael; Hafner, P. R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, PDF version.
Loz, E.; Širáň, J. (2008), "New record graphs in the degree-diameter problem", Australasian Journal of Combinatorics 41: 63–80.
Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, MR0140437, PDF version
Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly 75 (1): 42–43, MR0225679
Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey DS14 PDF version.

External links

Degree diameter problem on CombinatoricsWiki
Geoffrey Exoo's Degree-Diameter record graphs page.
Degree Diameter online table.
Vertex-symmetric digraphs online table.
Degree diameter problem on Wikipedia.