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

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

Below is the table of the vertex numbers for the best-known graphs (as of July 2022) 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 102038701321963366001250
4 1541983647401 3203 2437 57517 703
5 24722126242 7725 51617 03057 840187 056
6 3211139014047 91719 38376 461331 3871 253 615
7 501686722 75611 98852 768249 6601 223 0506 007 230
8 572531 1005 06039 672131 137734 8204 243 10024 897 161
9 745851 5508 26875 893279 6161 697 68812 123 28865 866 350
10 916502 28613 140134 690583 0834 293 45227 997 191201 038 922
11 1047153 20019 500156 8641 001 2687 442 32872 933 102600 380 000
12 1337864 68029 470359 7721 999 50015 924 326158 158 8751 506 252 500
13 1628566 56040 260531 4403 322 08029 927 790249 155 7603 077 200 700
14 1839168 20057 837816 2946 200 46055 913 932600 123 7807 041 746 081
15 1871 21511 71276 5181 417 2488 599 98690 001 2361 171 998 16410 012 349 898
16 2001 60014 640132 4961 771 56014 882 658140 559 4162 025 125 47612 951 451 931

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

ColorDetails
*The Petersen and Hoffman–Singleton graphs.
*Optimal graphs proven optimal by Elspas (1964).
*Optimal graph found by Wegner (1977) and proven optimal by Molodtsov (2006).
*Optimal graph found by Doty (1982) and proven optimal by Buset (2000).
*Graphs found by Robert M. Storwick
*Graph found by Bermond, Delorme & Farhi (1982).
*Graphs found by Delorme & Farhi (1984).
*Graphs found by Delorme (1985a).
*Graphs found by Delorme (1985b).
*Graphs found by Gómez & Fiol (1985).
*Graph found by Alegre, Fiol & Yebra (1986).
*Graph found by Allwright (1992).
*Graphs found by Gómez, Fiol & Serra (1993).
*Graph found by Comellas & Gómez (1994).
*Graph found by Dinneen & Hafner (1994)
*Graph found by Margarida Mitjana and Francesc Comellas in 1995, and independently by Sampels (1997).
*Graph found by Sampels (1997).
*Graphs found by Geoffrey Exoo from 1998 through 2010.
*McKay–Miller–Širáň graphs found by McKay, Miller & Širáň (1998).
*Graph found by Conder (2006).
*Graphs found by Pineda-Villavicencio et al. (2006).
*Graphs found by Loz & Širáň (2008).
*Graphs found by Gómez (2009).
*Graph found by Eduardo A. Canale in 2012.
*Graphs found by Canale & Rodríguez (2012).
*Graph found by Abas (2016).
*Graph found by Vlad Pelakhaty in 2021.

References
  • 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.
  • 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, 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.