In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a Moore graph is a
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...
whose
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
(the shortest
cycle length) is more than twice its
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
(the distance between the farthest two
vertices). If the
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
of such a graph is and its diameter is , its girth must equal . This is true, for a graph of degree and diameter , if and only if its number of vertices equals
:
an
upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an element ...
on the largest possible number of vertices in any graph with this degree and diameter. Therefore, these graphs solve the
degree diameter problem
In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is bounde ...
for their parameters.
Another equivalent definition of a Moore graph is that it has girth and precisely cycles of length , where and are, respectively, the numbers of vertices and edges of . They are in fact extremal with respect to the number of cycles whose length is the girth of the graph.
Moore graphs were named by 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
A cage is an enclosure often made of mesh, bars, or wires, used to confine, contain or protect something or someone. A cage can serve many purposes, including keeping an animal or person in captivity, capturing an animal or person, and displayin ...
. 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
Let be any graph with maximum degree and diameter , and consider the tree formed by
breadth first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next d ...
starting from any vertex . This tree has 1 vertex at level 0 ( itself), and at most vertices at level 1 (the neighbors of ). In the next level, there are at most vertices: each neighbor of uses one of its adjacencies to connect to and so can have at most neighbors at level 2. In general, a similar argument shows that at any level , there can be at most vertices. Thus, the total number of vertices can be at most
:
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 and diameter .
Later, showed that Moore graphs can equivalently be defined as having diameter and girth ; these two requirements combine to force the graph to be -regular for some 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
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
. Suppose has minimum degree and girth . Choose arbitrarily a starting vertex , and as before consider the breadth-first search tree rooted at . This tree must have one vertex at level 0 ( itself), and at least vertices at level 1. At level 2 (for ), there must be at least vertices, because each vertex at level 1 has at least 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 , there must be at least 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 : 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 levels of some breadth first search tree.
Therefore, any Moore graph has the minimum number of vertices possible among all graphs with minimum degree and girth : it is a
cage
A cage is an enclosure often made of mesh, bars, or wires, used to confine, contain or protect something or someone. A cage can serve many purposes, including keeping an animal or person in captivity, capturing an animal or person, and displayin ...
.
For even girth , 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 is
:
(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 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:
* The
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
s on nodes (diameter 1, girth 3, degree , order )
* The odd
cycles (diameter , girth , degree 2, order )
* The
Petersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...
(diameter 2, girth 5, degree 3, order 10)
* The
Hoffman–Singleton graph
In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7- regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman an ...
(diameter 2, girth 5, degree 7, order 50)
* A hypothetical graph of diameter 2, girth 5, degree 57 and order 3250, whose existence is unknown
Although all the known Moore graphs are
vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism
:f : G \to G\
such that
:f(v_1) = v_2.\
In other words, a graph is vertex-transitive i ...
s, 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.
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 polygon
In mathematics, a generalized polygon is an incidence structure introduced by Jacques Tits in 1959. Generalized ''n''-gons encompass as special cases projective planes (generalized triangles, ''n'' = 3) and generalized quadrangles (''n'' = 4). Ma ...
s. Some examples are the even cycles , the
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
s with girth four, the
Heawood graph Heawood is a surname. Notable people with the surname include:
* Jonathan Heawood, British journalist
*Percy John Heawood (1861–1955), British mathematician
**Heawood conjecture
** Heawood graph
**Heawood number In mathematics, the Heawood numbe ...
with degree 3 and girth 6, and the
Tutte–Coxeter graph
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore 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 for a generalized -gon.
See also
*
Table of the largest known graphs of a given diameter and maximal degree
Notes
References
*
*
* .
*
*
*.
*
*.
*
External links
*
Brouwer Brouwer (also Brouwers and de Brouwer) is a Dutch and Flemish surname. The word ''brouwer'' means 'beer brewer'.
Brouwer
* Adriaen Brouwer (1605–1638), Flemish painter
* Alexander Brouwer (b. 1989), Dutch beach volleyball player
* Andries Bro ...
and Haemers
Spectra of graphs* {{MathWorld2, urlname=MooreGraph, title=Moore Graph, urlname2=Hoffman-SingletonTheorem, title2=Hoffman-Singleton Theorem
Graph families
Regular graphs