Jump to content

Table of the largest known graphs of a given diameter and maximal degree

Add links
From Wikipedia, the free encyclopedia

In graph theory, the degree diameter problem is the problem of finding the largest possible graph for a given maximum degree and diameter. The Moore bound sets limits on this, but for many years mathematicians in the field have been interested in a more precise answer. The table below gives current progress on this problem (excluding the case of degree 2, where the largest graphs are cycles with an odd number of vertices).

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

[edit]

Below is the table of the vertex numbers for the best-known graphs (as of June 2024) in the undirected degree diameter problem for graphs of degree at most 3 ≤ d ≤ 16 and diameter 2 ≤ k ≤ 10. Only a few of the graphs in this table (marked in bold) are known to be optimal (that is, largest possible). The remainder are merely the largest so far discovered, 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.

k
d
2345678910
3 10[g 1]20[g 2]38[g 3]70[g 4]132[g 5]200[g 6]360[g 7]600[g 5]1250[g 8]
4 15[g 2]41[g 9]104[g 6]364[g 10]749[g 6]1 320[g 11]3 243[g 11]7 832[g 12]18 436[g 12]
5 24[g 2]72[g 5]252[g 13]650[g 14]2 820[g 12]5 896[g 12]17 724[g 12]59 294[g 12]190 578[g 12]
6 32[g 15]120[g 16]441[g 13]1 518[g 13]8 802[g 12]20 400[g 14]78 561[g 13]331 387[g 17]1 279 794[g 12]
7 50[g 18]170[g 13]684[g 16]2 810[g 12]12 642[g 19]56 952[g 13]255 938[g 12]1 227 774[g 12]6 128 958[g 12]
8 57[g 20]253[g 21]1 100[g 11]5 334[g 13]40 560[g 12]137 082[g 13]744 942[g 12]4 260 050[g 12]25 700 510[g 12]
9 74[g 20]585[g 10]1 640[g 22]8 802[g 23]77 418[g 12]298 840[g 13]1 859 260[g 12]12 441 690[g 12]80 560 386[g 12]
10 91[g 20]650[g 10]2 485[g 12]33 397[g 13]137 180[g 12]605 607[g 12]4 387 768[g 12]31 090 100[g 12]239 005 058[g 12]
11 106[g 12]715[g 10]3 444[g 12]37 628[g 12]186 033[g 12]1 153 512[g 12]9 261 072[g 12]74 391 834[g 13]634 001 048[g 12]
12 133[g 24]810[g 12]5 832[g 25]42 342[g 12]364 032[g 12]2 031 500[g 12]18 101 302[g 12]164 003 466[g 12]1 545 004 522[g 12]
13 162[g 26]873[g 12]6 615[g 12]51 417[g 12]535 302[g 12]3 528 248[g 13]35 140 224[g 13]334 485 050[g 13]3 480 003 090[g 12]
14 183[g 24]1 116[g 12]8 303[g 16]88 452[g 25]824 124[g 12]6 200 460[g 27]58 673 788[g 12]640 002 162[g 12]7 360 000 970[g 12]
15 190[g 12]1 539[g 13]11 785[g 12]100 000[g 25]1 424 474[g 12]9 372 780[g 12]98 108 874[g 12]1 200 000 050[g 12]13 600 000 810[g 12]
16 216[g 13]1 920[g 25]16 384[g 28]147 456[g 25]1 783 834[g 12]14 882 658[g 27]162 001 414[g 12]2 120 003 902[g 12]22 500 000 906[g 12]
  1. ↑ The Petersen graph.
  2. 1 2 3 Optimal graphs proven optimal by Elspas (1964).
  3. ↑ Optimal graph found by Doty (1982) and proven optimal by Buset (2000).
  4. ↑ Graph found by Alegre, Fiol & Yebra (1986).
  5. 1 2 3 Graphs found by Geoffrey Exoo from 1998 through 2010.
  6. 1 2 3 Graphs found by Nishant Bhakar in 2026 with Claude Fable assistance
  7. ↑ Graph found by Jianxiang Chen in 2018.
  8. ↑ Graph found by Conder (2006).
  9. ↑ Graph found by Allwright (1992).
  10. 1 2 3 4 Graphs found by Delorme (1985).
  11. 1 2 3 Graphs found by Eyal Loz in 2006
  12. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 Graphs found by Dharunish Yugeswardeenoo in 2026 using OpenAI GPT-5.6 Sol and Claude Fable 5 Max assistance
  13. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Graphs found by Rishabh Rajiv in 2026 using agentic coding systems
  14. 1 2 Graphs found by Rithwik Gupta in 2026 with AI-assisted computational searches
  15. ↑ Optimal graph found by Wegner (1977) and proven optimal by Molodtsov (2006).
  16. 1 2 3 Graphs found by Michel de Messieres in 2026 with Claude assistance
  17. ↑ Graph found by Canale & Rodríguez (2012).
  18. ↑ The Hoffman–Singleton graph.
  19. ↑ Graph found by Comellas (2024).
  20. 1 2 3 Graphs found by Storwick (1970).
  21. ↑ Graph found by Margarida Mitjana and Francesc Comellas in 1995, and independently by Sampels (1997).
  22. ↑ Graphs found by Comellas (2024).
  23. ↑ Graph found by Mark Marosi in 2026 with Claude assistance
  24. 1 2 Graphs found by Delorme & Farhi (1984).
  25. 1 2 3 4 5 Graphs found by Ryosuke Mizuno in 2026 using ChatGPT
  26. ↑ McKay–Miller–Širáň graph found by McKay, Miller & Širáň (1998).
  27. 1 2 Graphs found by Gómez, Fiol & Serra (1993).
  28. ↑ Graph found by a team of 6 people in 2026 using URSA (an agentic tool)

References

[edit]
  • Alegre, Ignacio; Fiol, Miquel; Yebra, J. Luis A. (1986), "Some Large Graphs with Given Degree and Diameter", Journal of Graph Theory, 10 (2): 219–224, doi:10.1002/jgt.3190100211
  • Comellas, Francesc (2024). "Table of large graphs with given degree and diameter". arXiv:2406.18994 [math.CO].
  • Doty, Karl (1982), "Large regular interconnection networks", Proceedings of the 3rd International Conference on Distributed Computing Systems, IEEE Computer Society, pp. 312–317
  • Elspas, Bernard (1964), "Topological constraints on interconnection-limited logic", 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 133–137, doi:10.1109/SWCT.1964.27
  • Molodtsov, Sergey (2006), General Theory of Information Transfer and Combinatorics, Springer, pp. 853–857, ISBN 978-3-540-46244-6
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree&oldid=1379783826"