The Degree Diameter Problem for General Graphs

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

[math]d[/math]\[math]k[/math]	2	3	4	5	6	7	8	9	10
3	10	20	38	70	132	196	360	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 697 688	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	856	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	200	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.
*	Graph found by Jianxiang Chen.
*	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).
*	Graph found by M. Abas. (2017). More details are available in a paper by the author.

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

[math]d[/math]\[math]k[/math]	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.87%	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

• Abas M., "Large Networks of Diameter Two Based on Cayley Graphs" in "Cybernetics and Mathematics Applications in Intelligent Systems, Advances in Intelligent Systems and Computing 574", (2017), Pages 225-233, PDF version
• 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

• Degree Diameter online table.
• Eyal Loz's Degree-Diameter problem page.
• Geoffrey Exoo's Degree-Diameter record graphs page.