Search datasets
Table of Large Degree/Diameter Graphs
Cite as:
2024-05-10T22:20:34.495+0200 Comellas, F (via Mendeley Data) 10.17632/d75dzbjd4k.2
A graph, G=(V,E), consists of a non empty finite set V of elements called vertices and a set E of pairs of elements of V called edges. The number of vertices N=|G|=|V| is the order of the graph. If (x,y) is an edge of E, we say that x and y (or y and x) are adjacent and this is usually written x --> y. It is also said that x and y are the endvertices of the edge (x,y). The degree of a vertex δ(x) is the number of vertices adjacent to x. The degree of G is Δ=max_{x ∈ V} δ(x). A graph is regular of degree Δ or Δ - regular if the degree of all vertices equal Δ. The distance between two vertices x and y, d(x,y) , is the number of edges of a shortest path between x and y , and its maximum value over all pair of vertices, D=max_{x, y ∈ V}d(x,y) , is the diameter of the graph. A (Δ,D) graph is a graph with maximum degree Δ and diameter at most D. The order of a graph with degree Δ, Δ > 2), of diameter D is easily seen to be bounded by1 + Δ + Δ (Δ-1) + ...+ Δ (Δ-1) D-1 = (Δ (Δ-1)D -2) / (Δ-2) = N(Δ, D)Hoffman and Singleton introduced the concept of Moore graphs, after Edward Forrest Moore, as graphs attaining this value, known as Moore bound. They also showed that, for D ≥ 2 and Δ ≥ 3, Moore graphs exist for D=2 and Δ =3,7 , and (perhaps) 57. In this context, it is of great interest to find graphs which for a given maximum diameter and maximum degree have a number of vertices as close as possible to the Moore bound.Download the package, unpack it and open in a browser the file table_degree_diameter.html or the file taula_delta_d.html.The table in this page gives the state of the art with respect to the LARGEST KNOWN (Δ ,D)-GRAPHS as in May 2024.Click the position if you wish to know more information: graph construction details, Moore bound, author, references... For most small (< 20000) order values you can download the adjacency list. Entries in boldface are optimal.
THIS DATASET IS ARCHIVED AT DANS/EASY, BUT NOT ACCESSIBLE HERE. TO VIEW A LIST OF FILES AND ACCESS THE FILES IN THIS DATASET CLICK ON THE DOI-LINK ABOVE