Moore graph

In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is Template:Mvar and its diameter is Template:Mvar, its girth must equal Template:Math. This is true, for a graph of degree Template:Mvar and diameter Template:Mvar, if and only if its number of vertices (its order) equals

$1+d\sum _{i=0}^{k-1}(d-1{)}^i,$

an upper bound on the largest possible number of vertices in any graph with this degree and diameter. Therefore, these graphs solve the degree diameter problem for their parameters.

Another equivalent definition of a Moore graph Template:Mvar is that it has girth Template:Math and precisely Template:Math cycles of length Template:Mvar, where Template:Mvar and Template:Mvar are, respectively, the numbers of vertices and edges of Template:Mvar. They are in fact extremal with respect to the number of cycles whose length is the girth of the graph.Template:Sfnp

Moore graphs were named by Template:Harvtxt 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.Template:Sfnp 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.

Bounding vertices by degree and diameter

The Petersen graph as a Moore graph. Any breadth-first search tree has Template:Math vertices in its Template:Mvar-th level for Template:Math.

Let Template:Mvar be any graph with maximum degree Template:Mvar and diameter Template:Mvar, and consider the tree formed by breadth-first search starting from any vertex Template:Mvar. This tree has 1 vertex at level 0 (Template:Mvar itself), and at most Template:Mvar vertices at level 1 (the neighbors of Template:Mvar). In the next level, there are at most Template:Math vertices: each neighbor of Template:Mvar uses one of its adjacencies to connect to Template:Mvar and so can have at most Template:Math neighbors at level 2. In general, a similar argument shows that at any level Template:Math, there can be at most Template:Math vertices. Thus, the total number of vertices can be at most

$1+d\sum _{i=0}^{k-1}(d-1{)}^i.$

Template:Harvtxt 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 Template:Mvar and diameter Template:Mvar.

Later, Template:Harvtxt showed that Moore graphs can equivalently be defined as having diameter Template:Mvar and girth Template:Math; these two requirements combine to force the graph to be Template:Mvar-regular for some Template:Mvar and to satisfy the vertex-counting formula.

Moore graphs as cages

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.Template:Sfnp Suppose Template:Mvar has minimum degree Template:Mvar and girth Template:Math. Choose arbitrarily a starting vertex Template:Mvar, and as before consider the breadth-first search tree rooted at Template:Mvar. This tree must have one vertex at level 0 (Template:Mvar itself), and at least Template:Mvar vertices at level 1. At level 2 (for Template:Math), there must be at least Template:Math vertices, because each vertex at level 1 has at least Template:Math 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 Template:Math, there must be at least Template:Math vertices. Thus, the total number of vertices must be at least

$1+d\sum _{i=1}^{k-1}(d-1{)}^i.$

In a Moore graph, this bound on the number of vertices is met exactly. Each Moore graph has girth exactly Template:Math: 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 Template:Mvar levels of some breadth-first search tree. Therefore, any Moore graph has the minimum number of vertices possible among all graphs with minimum degree Template:Mvar and girth Template:Math: it is a cage.

For even girth Template:Math, one can similarly form a breadth-first search tree starting from the midpoint of a single edge. The resulting bound on the minimum number of vertices in a graph of this girth with minimum degree Template:Mvar is

$2\sum _{i=0}^{k-1}(d-1{)}^i=1+(d-1{)}^{k-1}+d\sum _{i=0}^{k-2}(d-1{)}^i.$

(The right hand side of the formula instead counts the number of vertices in a breadth-first search tree starting from a single vertex, accounting for the possibility that a vertex in the last level of the tree may be adjacent to Template:Mvar vertices in the previous level.) Thus, the Moore graphs are sometimes defined as including the graphs that exactly meet this bound. Again, any such graph must be a cage.

Examples

The Hoffman–Singleton theorem states that any Moore graph with girth 5 must have degree 2, 3, 7, or 57. The Moore graphs are:Template:Sfnp

• The complete graphs Template:Mvar on Template:Math nodes (diameter 1, girth 3, degree Template:Math, order Template:Mvar)
• The odd cycles Template:Math (diameter Template:Mvar, girth Template:Math, degree 2, order Template:Math). This includes Template:Math with diameter 2, girth 5, degree 2, and order 5.
• The Petersen graph (diameter 2, girth 5, degree 3, order 10)
• The Hoffman–Singleton graph (diameter 2, girth 5, degree 7, order 50)
• A hypothetical graph (or more than one) of diameter 2, girth 5, degree 57 and order 3250; the existence of such is unknown and is one of the most famous open problems in graph theory.Template:Sfnp

Although all the known Moore graphs are vertex-transitive graphs, the unknown one (if it exists) cannot be vertex-transitive, as its automorphism group can have order at most 375, less than its number of vertices.Template:Sfnp

If the generalized definition of Moore graphs that allows even girth graphs is used, the even girth Moore graphs correspond to incidence graphs of (possible degenerate) generalized polygons. Some examples are the even cycles Template:Math, the complete bipartite graphs Template:Math with girth four, the Heawood graph with degree 3 and girth 6, and the Tutte–Coxeter graph with degree 3 and girth 8. More generally it is known that, other than the graphs listed above, all Moore graphs must have girth 5, 6, 8, or 12. The even girth case also follows from the Feit-Higman theorem about possible values of Template:Mvar for a generalized Template:Mvar-gon.

See also

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

References

• Template:Citation
• Template:Citation
• Template:Citation.
• Template:Citation
• Template:Citation
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation

External links

• Brouwer and Haemers: Spectra of graphs
• Template:MathWorld2