Moore graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
List of unsolved problems in mathematics
Does a Moore graph with girth 5 and degree 57 exist?

In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound

1+d\sum_{i=0}^{k-1}(d-1)^i .

An equivalent definition of a Moore graph is that it is a graph of diameter k with girth 2k + 1. 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.

Bounding vertices by degree and diameter[edit]

The Petersen graph as a Moore graph. Any breadth first search tree has d(d-1)i vertices in its ith level.

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 ≤ ik, there can be at most d(d-1)i vertices. Thus, the total number of vertices can be at most

1+d\sum_{i=0}^{k-1}(d-1)^i.

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.

Moore graphs as cages[edit]

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 ≤ ik, there must be at least d(d-1)i vertices. Thus, the total number of vertices must be at least

1+d\sum_{i=0}^{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 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.

For even girth 2k, 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 d 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 d 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[edit]

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

  • The complete graphs  K_n on n > 2 nodes. (diameter 1, girth 3, degree n-1, order n)
  • The odd cycles  C_{2n+1} . (diameter n, girth 2n+1, degree 2, order 2n+1)
  • A hypothetical graph of diameter 2, girth 5, degree 57 and order 3250; it is currently unknown whether such a graph exists.

Unlike all other Moore graphs, Higman proved that the unknown Moore graph cannot be vertex-transitive.

If the generalized definition of Moore graphs that allows even girth graphs is used, the Moore graphs also include the even cycles  C_{2n} , the complete bipartite graphs  K_{n,n} 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 (Bannai & Ito 1973; Damerell 1973) that, other than the graphs listed above, all Moore graphs must have girth 5, 6, 8, or 12.

See also[edit]

References[edit]

External links[edit]