Moore graph

In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound An equivalent definition of a Moore graph is that it is a graph of diameter k {displaystyle k} with girth 2 k + 1 {displaystyle 2k+1} . Another equivalent definition of a Moore graph G {displaystyle G} is that it has girth g = 2 k + 1 {displaystyle g=2k+1} and precisely n g ( m − n + 1 ) {displaystyle {frac {n}{g}}(m-n+1)} cycles of length g {displaystyle g} , where n {displaystyle n} and m {displaystyle m} are, respectively, the numbers of vertices and edges of G {displaystyle G} . They are in fact extremal with respect to the number of cycles whose length is the girth of the graph (Azarija & Klavžar 2015). Moore graphs were named by Hoffman & Singleton (1960) after Edward F. Moore, who posed the question of describing and classifying these graphs. As well as having the maximum possible number of vertices for a given combination of degree and diameter,Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage (Erdős, Rényi & Sós 1966). The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth as well as odd girth, and again these graphs are cages. Let G be any graph with maximum degree d and diameter k, and consider the tree formed by breadth first search starting from any vertex v. This tree has 1 vertex at level 0 (v itself), and at most d vertices at level 1 (the neighbors of v). In the next level, there are at most d(d-1) vertices: each neighbor of v uses one of its adjacencies to connect to v and so can have at most d-1 neighbors at level 2. In general, a similar argument shows that at any level 1 ≤ i ≤ k, there can be at most d(d-1)i vertices. Thus, the total number of vertices can be at most Hoffman & Singleton (1960) originally defined a Moore graph as a graph for which this bound on the number of vertices is met exactly. Therefore, any Moore graph has the maximum number of vertices possible among all graphs with maximum degree d and diameter k. Later, Singleton (1968) showed that Moore graphs can equivalently be defined as having diameter k and girth 2k+1; these two requirements combine to force the graph to be d-regular for some d and to satisfy the vertex-counting formula. Instead of upper bounding the number of vertices in a graph in terms of its maximum degree and its diameter, we can calculate via similar methods a lower bound on the number of vertices in terms of its minimum degree and its girth (Erdős, Rényi & Sós 1966). Suppose G has minimum degree d and girth 2k+1. Choose arbitrarily a starting vertex v, and as before consider the breadth-first search tree rooted at v. This tree must have one vertex at level 0 (v itself), and at least d vertices at level 1. At level 2 (for k > 1), there must be at least d(d-1) vertices, because each vertex at level 1 has at least d-1 remaining adjacencies to fill, and no two vertices at level 1 can be adjacent to each other or to a shared vertex at level 2 because that would create a cycle shorter than the assumed girth. In general, a similar argument shows that at any level 1 ≤ i ≤ k, there must be at least d(d-1)i vertices. Thus, the total number of vertices must be at least In a Moore graph, this bound on the number of vertices is met exactly. Each Moore graph has girth exactly 2k+1: it does not have enough vertices to have higher girth, and a shorter cycle would cause there to be too few vertices in the first k levels of some breadth first search tree.Therefore, any Moore graph has the minimum number of vertices possible among all graphs with minimum degree d and diameter k: it is a cage.