The Degree Diameter Problem for General Graphs

From Combinatorics Wiki

Jump to: navigation, search

Contents

Introduction

The degree/diameter problem for general graphs can be stated as follows:

Given natural numbers d and k, find the largest possible number N(d,k) of vertices in a graph of maximum degree d and diameter k.

In attempting to settle the values of N(d,k), research activities in this problem have follow the following two directions:

  • Increasing the lower bounds for N(d,k) by constructing ever larger graphs.
  • Lowering and/or setting upper bounds for N(d,k) by proving the non-existence of graphs

whose order is close to the Moore bounds M(d,k)=(d(d-1)k-2)(d-2)-1.

Increasing the lower bounds for N(d,k)

In the quest for the largest known graphs many innovative approaches have been suggested. In a wide spectrum, we can classify these approaches into general (those producing graphs for many combinations of the degree and the diameter) and ad hoc (those devised specifically for producing graphs for few combinations of the degree and the diameter). Among the former, we have the constructions of De Bruijn graphs and Kautz graphs, while among the latter, we have the star product, the voltage assigment technique and graph compunding. For information on the state-of -the-art of this research stream, the interested reader is referred to the survey by Miller and Širáň.

Below is the table of the largest known graphs (as of September 2009) in the undirected degree diameter problem for graphs of degree at most 3 ≤ d ≤ 20 and diameter 2 ≤ k ≤ 10. Only a few of the graphs in this table are known to be optimal (marked in bold), and thus, finding a larger graph that is closer in order (in terms of the size of the vertex set) to the Moore bound is considered an open problem. Some general constructions are known for values of d and k outside the range shown in the table.


Table of the orders of the largest known graphs for the undirected degree diameter problem

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 98 364 740 1 320 3 243 7 575 17 703
5 24 72 212 624 2 772 5 516 17 030 57 840 187 056
6 32 111 390 1 404 7 917 19 383 76 461 331 387 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 268 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 187 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
17 274 1 610 19 040 133 144 3 217 872 18 495 162 220 990 700 3 372 648 954 15 317 070 720
18 307 1 620 23 800 171 828 4 022 340 26 515 120 323 037 476 5 768 971 167 16 659 077 632
19 338 1 638 23 970 221 676 4 024 707 39 123 116 501 001 000 8 855 580 344 18 155 097 232
20 381 1 958 34 952 281 820 8 947 848 55 625 185 762 374 779 12 951 451 931 78 186 295 824

The following table is the key to the colors in the table presented above:

Color Details
* The Petersen and Hoffman–Singleton graphs.
* Other non Moore but optimal graphs.
* Graph found by J. Allwright.
* Graph found by G. Wegner.
* Graphs found by G. Exoo.
* Family of graphs found by B. D. McKay, M. Miller and J. Širáň. More details are available in a paper by the authors.
* Graphs found by J. Gómez.
* Graph found by M. Mitjana and F. Comellas. This graph was also found independently by M. Sampels.
* Graphs found by C. Delorme.
* Graphs found by C. Delorme and G. Farhi.
* Graphs found by E. Canale. (2012)
* Graph found by J. C. Bermond, C. Delorme, and G. Farhi
* Graphs found by J. Gómez and M. A. Fiol.
* Graphs found by J. Gómez, M. A. Fiol, and O. Serra.
* Graph found by M.A. Fiol and J.L.A. Yebra.
* Graph found by F. Comellas and J. Gómez.
* Graphs found by G. Pineda-Villavicencio, J. Gómez, M. Miller and H. Pérez-Rosés. More details are available in a paper by the authors.
* Graphs found by E. Loz. More details are available in a paper by E. Loz and J. Širáň.
* Graphs found by E. Loz and G. Pineda-Villavicencio. More details are available in a paper by the authors.
* Graphs found by A. Rodriguez. (2012)
* Graphs found by M. Sampels.
* Graphs found by M. J. Dinneen and P. Hafner. More details are available in a paper by the authors.
* Graph found by M. Conder.
* Graphs found by Brown, W. G. (1966).

Lowering and/or setting upper bounds for N(d,k)

As the Moore bound cannot be reached in general, some theoretical work has been done to determine the lowest possible upper bounds. In this direction reserachers have been interested in graphs of maximum degree d, diameter k and order M(d,k)-δ for small δ. The parameter δ is called the defect. Such graphs are called (d,k,-δ)-graphs.

For δ=1 the only (d,k,-1)-graphs are the cycles on 2k vertices. Erdös, Fajtlowitcz and Hoffman, who proved the non-existence of (d,2,-1)-graphs for d≠3. Then, Bannai and Ito, and also independently, Kurosawa and Tsujii, proved the non-existence of (d,k,-1)-graphs for d≥3 and k≥3.

For δ=2, the (2,k,-2)-graphs are the cycles on 2k-1. Considering d≥3, only five graphs are known at present. Elspas found the unique (4,2,-2)-graph and the unique (5,2,-2)-graph, and credited Green with producing the unique (3,3,-2)-graph. The other graphs are two non-isomorphic (3,2,-2)-graphs.

When δ=2, d≥3 and k≥3, not much is known about the existence or otherwise of (d,k,-2)-graphs. In this context some known outcomes include the non-existence of (3,k,-2)-graphs with k≥4 by Leif Jorgensen, the non-existence of (4,k,-2)-graphs with k≥3 by Mirka Miller and Rino Simanjuntak, some structural properties of (5,k,-2)-graphs with k≥3 by Guillermo Pineda-Villavicencio and Mirka Miller, the obtaining of several necessary conditions for the existence of (d,2,-2)-graphs with d≥3 by Mirka Miller, Minh Nguyen and Guillermo Pineda-Villavicencio, and the non-existence of (d,2,-2)-graphs for 5<d<50 by Jose Conde and Joan Gimbert.

For the case of δ≥3 only a few works are known at present: the non-existence of (3,4,-4)-graphs by Leif Jorgensen; the complete catalogue of (3,k,-4)-graphs with k≥2 by Guillermo Pineda-Villavicencio and Mirka Miller by proving the non-existence of (3,k,-4)-graphs with k≥5, the settlement of N(3,4)=M(3,4)=38 by Buset; and the obtaining of N(6,2)=M(6,2)-5=32 by Molodtsov. For more information, check the corresponding papers, and the survey by Miller and Širáň.

Table of the lowest upper bounds known at present, and the percentage of the order of the largest known graphs

d\k 2 3 4 5 6 7 8 9 10
3
10
100%
20
100%
38
100%
92
76.08%
188
70.21%
380
51.57%
764
43.97%
1532
39.16%
3068
40.74%
4
15
100%
52
78.84%
160
61.25%
484
75.20%
1456
50.82%
4372
30.19%
13120
24.71%
39364
19.24%
118096
14.99%
5
24
100%
104
69.23%
424
50%
1704
36.61%
6824
40.62%
27304
20.20%
109224
15.59%
436904
13.23%
1747624
10.70%
6
32
100%
186
59.67%
936
41.66%
4686
29.96%
23436
33.78%
117186
16.54%
585936
13.04%
2929686
10.50%
14648436
8.55%
7
50
100%
301
55.81%
1813
37.06%
10885
25.31%
65317
18.35%
391909
13.46%
2351461
10.61%
14108773
8.66%
84652645
7.09%
8
63
90.47%
456
55.48%
3200
34.37%
22408
22.58%
156864
25.29%
1098056
11.94%
7686400
9.56%
53804808
7.88%
376633664
6.61%
9
80
92.50%
657
89.04%
5265
29.43%
42129
19.46%
337041
22.51%
2696337
10.37%
21570705
7.81%
172565649
7.02%
1380525201
4.77%
10
99
91.91%
910
71.42%
8200
27.87%
73810
17.80%
664300
20.27%
5978710
9.75%
53808400
7.97%
484275610
5.78%
4358480500
4.61%
11
120
86.66%
1221
58.55%
12221
26.18%
122221
15.95%
1222221
12.83%
12222221
8.19%
122222221
6.08%
1222222221
5.96%
12222222221
4.91%
12
143
93%
1596
49.24%
17568
26.63%
193260
15.24%
2125872
16.92%
23384604
8.55%
257230656
6.19%
2829537228
5.58%
31124909520
4.83%
13
168
96.42%
2041
41.69%
24505
26.77%
294073
13.69%
3528889
15.05%
42346681
7.84%
508160185
5.88%
6097922233
4.08%
73175066809
4.20%
14
195
93.84%
2562
35.75%
33320
24.60%
433174
13.35%
5631276
14.49%
73206602
8.46%
951685840
5.87%
12371915934
4.85%
160834907156
4.37%
15
224
83.03%
3165
38.38%
44325
26.42%
620565
12.33%
8687925
16.31%
121630965
7.07%
1702833525
5.28%
23839669365
4.91%
333755371125
2.99%
16
255
77.64%
3856
41.49%
57856
25.30%
867856
15.26%
13017856
13.60%
195267856
7.62%
2929017856
4.79%
43935267856
4.60%
659029017856
1.96%
17
288
95.13%
4641
34.69%
74273
25.63%
1188385
11.20%
19014177
16.92%
304226849
6.07%
4867629601
4.54%
77882073633
4.33%
1246113178145
1.22%
18
323
95.04%
5526
29.31%
93960
25.32%
1597338
10.75%
27154764
14.81%
461631006
5.74%
7847727120
4.11%
133411361058
4.32%
2267993138004
0.73%
19
360
93.88%
6517
25.13%
117325
20.43%
2111869
10.49%
38013661
10.58%
684245917
5.71%
12316426525
4.06%
221695677469
3.99%
3990522194461
0.45%
20
399
95.48%
7620
25.69%
144800
24.13%
2751220
10.24%
52273200
17.11%
993190820
5.6%
18870625600
4.04%
358541886420
3.61%
6812295842000
1.14%


The following table is the key to the colors in the table presented above:

Color Details
* The Moore bound.
* Upper bound introduced by A. Hoffman, R. Singleton, Bannai, E. and Ito, T.
* Upper bound introduced by Leif Jorgensen.
* Optimal graphs found by Buset and by Molodtsov.
* Graphs shown optimal.

References

  • Bannai, E.; Ito, T. (1981), "Regular graphs with excess one", Discrete Mathematics 37:147-158, doi:10.1016/0012-365X(81)90215-6.
  • Buset, D. (2000), "Maximal cubic graphs with diameter 4", Discrete Applied Mathematics 101 (1-3): 53-61, doi:10.1016/S0166-218X(99)00204-8.
  • J. Dinneen, Michael; Hafner, P. R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, PDF version.
  • Elspas, B. (1964), "Topological constraints on interconnection-limited logic", Proceedings of IEEE Fifth Symposium on Switching Circuit Theory and Logical Design S-164: 133--147.
  • Erdös P; Fajtlowicz, S.; Hoffman A. J. (1980), "Maximum degree in graphs of diameter 2", Networks 10: 87-90.
  • Hoffman, A. J.; Singleton, R. R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, MR0140437, PDF version.
  • L. K. Jorgensen (1992), "Diameters of cubic graphs", Discrete Applied Mathematics 37/38: 347-351, doi:10.1016/0166-218X(92)90144-Y.
  • L. K. Jorgensen (1993), "Nonexistence of certain cubic graphs with small diameters", Discrete Mathematics 114:265-273, doi:10.1016/0012-365X(93)90371-Y.
  • Kurosawa, K.; Tsujii, S. (1981), "Considerations on diameter of communication networks", Electronics and Communications in Japan 64A (4): 37-45.
  • Loz, E.; Širáň, J. (2008), "New record graphs in the degree-diameter problem", Australasian Journal of Combinatorics 41: 63–80.
  • Loz, E.; Pineda-Villavicencio, G. (2010), "New benchmarks for large scale networks with given maximum degree and diameter", The Computer Journal, The British Computer Society, Oxford University Press.
  • McKay, B. D.; Miller, M.; Širáň, J. (1998), "A note on large graphs of diameter two and given maximum degree", Journal of Combinatorial Theory Series B 74 (4): 110–118.
  • Miller, M; Nguyen, M.; Pineda-Villavicencio, G. (accepted in September 2008), "On the nonexistence of graphs of diameter 2 and defect 2", Journal of Combinatorial Mathematics and Combinatorial Computing.
  • Miller, M.; Simanjuntak, R. (2008), "Graphs of order two less than the Moore bound", Discrete Mathematics 308 (13): 2810-2821, doi:10.1016/j.disc.2006.06.045.
  • Miller, M.; Širáň, J. (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey D, PDF version.
  • Molodtsov, S. G. (2006), "Largest Graphs of Diameter 2 and Maximum Degree 6", Lecture Notes in Computer Science 4123: 853-857.
  • Pineda-Villavicencio, G.; Miller, M. (2008), "On graphs of maximum degree 3 and defect 4", Journal of Combinatorial Mathematics and Combinatorial Computing 65: 25-31.
  • Pineda-Villavicencio, G.; Miller, M., "Complete characterization of graphs of maximum degree 3 and defect at most 4", submitted.
  • Pineda-Villavicencio, G.; Gómez, J.; Miller, M.; Pérez-Rosés, H., "New Largest Known Graphs of Diameter 6", Networks, to appear, doi:10.1002/net.20269. See also Electronic Notes in Discrete Mathematics 24: 153–160, 2006.
  • Pineda-Villavicencio, G.; Miller, M. (Oct 2006), "On Graphs of Maximum Degree 5, Diameter D and Defect 2", Proceedings of MEMICS 2006, Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science: 182--189, Mikulov, Czech Republic.
  • Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canadian Mathematical Bulletin, 9, 281 - 285.

External links