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 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.

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:

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.
  • Comellas, Francesc (2024). "Table of large graphs with given degree and diameter". arXiv:2406.18994.
  • 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree&oldid=1273130587"
Uses material from the Wikipedia article Table of the largest known graphs of a given diameter and maximal degree, released under the CC BY-SA 4.0 license.