Edge Rewrite
everything Source code View original
// HTMLRewriter · presentation

This page was redesigned at the edge.

Cloudflare fetched the original article and streamed it through HTMLRewriter to apply an entirely new visual system without rebuilding the source page.

// request.cf · coarse context

A page that knows where it met you.

Only coarse request metadata is shown. This demo does not display or persist visitor IP addresses.

Country
US
Cloudflare location
CMH
Connection
HTTP/2
Language
Not provided

Ray ID: a22b6ee16eaacf84

Jump to content

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

Add links
From Wikipedia, the free encyclopedia
(Redirected from Table of graphs)

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]196[g 5]360[g 6]600[g 5]1250[g 7]
4 15[g 2]41[g 8]98[g 5]364[g 9]740[g 10]1 3203 2437 57517 703
5 24[g 2]72[g 5]212[g 5]6242 772[g 11]5 51617 03057 840187 056
6 32[g 12]111[g 5]39014047 917[g 11]19 38376 891[g 13]331 387[g 14]1 253 615
7 50[g 15]168[g 5]672[g 16]2 756[g 17]12 264[g 13]53 020[g 13]249 6601 223 0506 007 230
8 57[g 18]253[g 19]1 1005 115[g 13]39 672[g 20]131 137734 8204 243 10024 897 161
9 74[g 18]585[g 9]1 640[g 13]8 268[g 14]75 893[g 11]279 6161 697 688[g 14]12 123 28865 866 350
10 91[g 18]650[g 9]2 331[g 13]13 203[g 13]134 690[g 20]583 0834 293 45227 997 191201 038 922
11 104[g 5]715[g 9]3 200[g 21]19 620[g 13]156 864[g 21]1 001 2687 442 32872 933 102600 380 000
12 133[g 22]786[g 20]4 680[g 23]29 621[g 13]359 772[g 11]1 999 50015 924 326158 158 8751 506 252 500
13 162[g 24]856[g 25]6 560[g 21]40 488[g 13]531 440[g 21]3 322 08029 927 790249 155 7603 077 200 700
14 183[g 22]916[g 20]8 200[g 21]58 095[g 13]816 294[g 11]6 200 460[g 26]55 913 932600 123 7807 041 746 081
15 187[g 27]1 215[g 28]11 712[g 21]77 520[g 13]1 417 248[g 21]8 599 98690 001 2361 171 998 16410 012 349 898
16 200[g 29]1 600[g 28]14 640[g 21]132 496[g 28]1 771 560[g 21]14 882 658[g 26]140 559 4162 025 125 47612 951 451 931

Entries without a footnote were found by Loz & Širáň (2008). In all other cases, the footnotes in the table indicate the origin of the graph that achieves the given number of vertices:

  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 4 5 6 7 8 9 Graphs found by Geoffrey Exoo from 1998 through 2010.
  6. ↑ Graph found by Jianxiang Chen in 2018.
  7. ↑ Graph found by Conder (2006).
  8. ↑ Graph found by Allwright (1992).
  9. 1 2 3 4 Graphs found by Delorme (1985a).
  10. ↑ Graph found by Comellas & Gómez (1994).
  11. 1 2 3 4 5 Graphs found by Pineda-Villavicencio et al. (2006).
  12. ↑ Optimal graph found by Wegner (1977) and proven optimal by Molodtsov (2006).
  13. 1 2 3 4 5 6 7 8 9 10 11 12 Graphs found by Comellas (2024).
  14. 1 2 3 Graphs found by Canale & Rodríguez (2012).
  15. ↑ The Hoffman–Singleton graph.
  16. ↑ Graph found by Sampels (1997).
  17. ↑ Graph found by Dinneen & Hafner (1994).
  18. 1 2 3 Graphs found by Storwick (1970).
  19. ↑ Graph found by Margarida Mitjana and Francesc Comellas in 1995, and independently by Sampels (1997).
  20. 1 2 3 4 Graphs found by Gómez (2009).
  21. 1 2 3 4 5 6 7 8 9 Graphs found by Gómez & Fiol (1985).
  22. 1 2 Graphs found by Delorme & Farhi (1984).
  23. ↑ Graph found by Bermond, Delorme & Farhi (1982).
  24. ↑ McKay–Miller–Širáň graphs found by McKay, Miller & Širáň (1998).
  25. ↑ Graph found by Vlad Pelakhaty in 2021.
  26. 1 2 Graphs found by Gómez, Fiol & Serra (1993).
  27. ↑ Graph found by Eduardo A. Canale in 2012.
  28. 1 2 3 Graphs found by Delorme (1985b).
  29. ↑ Graph found by Abas (2016).

References

[edit]
  • Abas, Marcel (2016), "Cayley graphs of diameter two with order greater than 0.684 of the Moore bound for any degree", European Journal of Combinatorics, 57: 109–120, arXiv:1511.03706, doi:10.1016/j.ejc.2016.04.008
  • Comellas, Francesc; Gómez, José (1994). "New Large Graphs with Given Degree and Diameter". arXiv:math/9411218.
  • 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
  • Gómez, José (2009), "Some new large (Δ, 3)-graphs", Networks, 53 (1): 1–5, doi:10.1002/NET.V53:1
  • Gómez, José; Fiol, Miquel (1985), "Dense compound graphs", Ars Combinatoria, 20: 211–237
  • Molodtsov, Sergey (2006), General Theory of Information Transfer and Combinatorics, Springer, pp. 853–857, ISBN 978-3-540-46244-6
  • Sampels, Michael (1997), "Large Networks with Small Diameter", Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 1335, Springer, Berlin, Heidelberg, pp. 288–302, doi:10.1007/BFb0024505, ISBN 978-3-540-69643-8
[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=1365867998"