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

Last updated

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

Contents

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.

k
d
2345678910
310 [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]
415 [g 2] 41 [g 8] 98 [g 5] 364 [g 9] 740 [g 10] 1 3203 2437 57517 703
524 [g 2] 72 [g 5] 212 [g 5] 6242 772 [g 11] 5 51617 03057 840187 056
632 [g 12] 111 [g 5] 39014047 917 [g 11] 19 38376 891 [g 13] 331 387 [g 14] 1 253 615
750 [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
857 [g 18] 253 [g 19] 1 1005 115 [g 13] 39 672 [g 20] 131 137734 8204 243 10024 897 161
974 [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
1091 [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
11104 [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
12133 [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
13162 [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
14183 [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
15187 [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
16200 [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).

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

<span class="mw-page-title-main">Pancake sorting</span> Mathematics problem

Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Diameter (graph theory)</span> Longest distance between two vertices

In graph theory, the diameter of a connected undirected graph is the farthest distance between any two of its vertices. That is, it is the diameter of a set for the set of vertices of the graph, and for the shortest-path distance in the graph. Diameter may be considered either for weighted or for unweighted graphs. Researchers have studied the problem of computing the diameter, both in arbitrary graphs and in special classes of graphs.

<span class="mw-page-title-main">Brendan McKay (mathematician)</span> Australian mathematician

Brendan Damien McKay is an Australian computer scientist and mathematician. He is currently an Emeritus Professor in the Research School of Computer Science at the Australian National University (ANU). He has published extensively in combinatorics.

<span class="mw-page-title-main">Václav Chvátal</span> Czech-Canadian mathematician

Václav (Vašek) Chvátal is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

<span class="mw-page-title-main">Boxicity</span> Smallest dimension where a graph can be represented as an intersection graph of boxes

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraphH, denoted L(H), is the graph whose vertex set is the set of the hyperedges of H, with two vertices adjacent in L(H) when their corresponding hyperedges have a nonempty intersection in H. In other words, L(H) is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph.

<span class="mw-page-title-main">Strong orientation</span>

In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge that makes it into a strongly connected graph.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In graph theory, the degree diameter problem is the problem of finding the largest possible graph G of diameter k such that the largest degree of any of the vertices in G is at most d. The size of G is bounded above by the Moore bound; for 1 < k and 2 < d, only the Petersen graph, the Hoffman-Singleton graph, and possibly graphs of diameter k = 2 and degree d = 57 attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound.

The best known vertex transitive digraphs in the directed Degree diameter problem are tabulated below.

<span class="mw-page-title-main">Greedy coloring</span> One-by-one assignment of colors to graph vertices

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

<span class="mw-page-title-main">Turán's brick factory problem</span> On minimizing crossings in bicliques

In the mathematics of graph drawing, Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. The problem is named after Pál Turán, who formulated it while being forced to work in a brick factory during World War II.

The Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS) is a problem in graph theory.

Dominique de Caen was a mathematician, Doctor of Mathematics, and professor of Mathematics, who specialized in graph theory, probability theory, and information theory. He is renowned for his research on Turán's extremal problem for hypergraphs.

Mirka Miller was a Czech-Australian mathematician and computer scientist interested in graph theory and data security. She was a professor of electrical engineering and computer science at the University of Newcastle.

In graph theory, the McKay–Miller–Širáň graphs are an infinite class of vertex-transitive graphs with diameter two, and with a large number of vertices relative to their diameter and degree. They are named after Brendan McKay, Mirka Miller, and Jozef Širáň, who first constructed them using voltage graphs in 1998.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.