The Degree/Diameter Problem

From

Jump to: navigation, search

Contents

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 (dk+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 Nb(d,k) (for bipartite graphs), Nvt(d,k) (for vertex-transitive graphs), Nc(d,k) (for Cayley graphs), and Nat(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 Z2, 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