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 by
1 + Δ + Δ (Δ-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, see [HoSi60]. 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.
The following table give the state of the art with respect to the LARGEST KNOWN (Δ ,D)-GRAPHS
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.
Link to a Java applet that computes the degree and diameter of a graph in a file, local or accessible by HTTP, and formatted as a list of adjacencies. Click here.
References
Related problems are: