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 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
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 461331 387 [g 13] 1 253 615
750 [g 14] 168 [g 5] 672 [g 15] 2 756 [g 16] 11 98852 768249 6601 223 0506 007 230
857 [g 17] 253 [g 18] 1 1005 06039 672 [g 19] 131 137734 8204 243 10024 897 161
974 [g 17] 585 [g 9] 1 5508 268 [g 13] 75 893 [g 11] 279 6161 697 688 [g 13] 12 123 28865 866 350
1091 [g 17] 650 [g 9] 2 28613 140134 690 [g 19] 583 0834 293 45227 997 191201 038 922
11104 [g 5] 715 [g 9] 3 200 [g 20] 19 500156 864 [g 20] 1 001 2687 442 32872 933 102600 380 000
12133 [g 21] 786 [g 19] 4 680 [g 22] 29 470359 772 [g 11] 1 999 50015 924 326158 158 8751 506 252 500
13162 [g 23] 856 [g 24] 6 560 [g 20] 40 260531 440 [g 20] 3 322 08029 927 790249 155 7603 077 200 700
14183 [g 21] 916 [g 19] 8 200 [g 20] 57 837816 294 [g 11] 6 200 460 [g 25] 55 913 932600 123 7807 041 746 081
15187 [g 26] 1 215 [g 27] 11 712 [g 20] 76 5181 417 248 [g 20] 8 599 98690 001 2361 171 998 16410 012 349 898
16200 [g 28] 1 600 [g 27] 14 640 [g 20] 132 496 [g 27] 1 771 560 [g 20] 14 882 658 [g 25] 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 Cheng 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 Graphs found by Canale & Rodríguez (2012).
  14. ↑ The Hoffman–Singleton graph.
  15. ↑ Graph found by Sampels (1997).
  16. ↑ Graph found by Dinneen & Hafner (1994).
  17. 1 2 3 Graphs found by Storwick (1970).
  18. ↑ Graph found by Margarida Mitjana and Francesc Comellas in 1995, and independently by Sampels (1997).
  19. 1 2 3 4 Graphs found by Gómez (2009).
  20. 1 2 3 4 5 6 7 8 9 Graphs found by Gómez & Fiol (1985).
  21. 1 2 Graphs found by Delorme & Farhi (1984).
  22. ↑ Graph found by Bermond, Delorme & Farhi (1982).
  23. ↑ McKay–Miller–Širáň graphs found by McKay, Miller & Širáň (1998).
  24. ↑ Graph found by Vlad Pelakhaty in 2021.
  25. 1 2 Graphs found by Gómez, Fiol & Serra (1993).
  26. ↑ Graph found by Eduardo A. Canale in 2012.
  27. 1 2 3 Graphs found by Delorme (1985b).
  28. ↑ Graph found by Abas (2016).

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in 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">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">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.

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.

In graph theory, the graph bandwidth problem is to label the n vertices vi of a graph G with distinct integers so that the quantity is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.

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

Hunter Snevily (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.

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.