In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
area of
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 conn ...
, a cage 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 outdegr ...
that has as few
vertices as possible for its
girth.
Formally, an is defined to be a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
in which each vertex has exactly neighbors, and in which the shortest
cycle has length exactly .
An is an with the smallest possible number of vertices, among all . A is often called a .
It is known that an exists for any combination of and . It follows that all exist.
If a
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 and its diameter is , its girth must ...
exists with degree and girth , it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth must have at least
:
vertices, and any cage with even girth must have at least
:
vertices. Any with exactly this many vertices is by definition a Moore graph and therefore automatically a cage.
There may exist multiple cages for a given combination of and . For instance there are three nonisomorphic , each with 70 vertices: the
Balaban 10-cage, the
Harries graph and the
Harries–Wong graph. But there is only one : the
Balaban 11-cage (with 112 vertices).
Known cages
A 1-regular graph has no cycle, and a connected 2-regular graph has girth equal to its number of vertices, so cages are only of interest for ''r'' ≥ 3. The (''r'',3)-cage is a
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 ...
''K''
''r''+1 on ''r''+1 vertices, and the (''r'',4)-cage is a
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 i ...
''K''
''r'',''r'' on 2''r'' vertices.
Notable cages include:
* (3,5)-cage: 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 ...
, 10 vertices
* (3,6)-cage: 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 ...
, 14 vertices
* (3,7)-cage: the
McGee graph, 24 vertices
* (3,8)-cage: 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 ...
, 30 vertices
* (3,10)-cage: the
Balaban 10-cage, 70 vertices
* (3,11)-cage: the
Balaban 11-cage, 112 vertices
* (4,5)-cage: the
Robertson graph
In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4- regular undirected graph with 19 vertices and 38 edges named after Neil Robertson.
The Robertson graph is the unique (4,5)-cage graph and was discovered by Rob ...
, 19 vertices
* (7,5)-cage: 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 ...
, 50 vertices.
* When ''r'' − 1 is a prime power, the (''r'',6) cages are the incidence graphs of
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
s.
* When ''r'' − 1 is a prime power, the (''r'',8) and (''r'',12) cages are
generalized polygons.
The numbers of vertices in the known (''r'',''g'') cages, for values of ''r'' > 2 and ''g'' > 2, other than projective planes and generalized polygons, are:
Asymptotics
For large values of ''g'', the Moore bound implies that the number ''n'' of vertices must grow at least
singly exponentially as a function of ''g''. Equivalently, ''g'' can be at most proportional to the
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
of ''n''. More precisely,
:
It is believed that this bound is tight or close to tight . The best known lower bounds on ''g'' are also logarithmic, but with a smaller constant factor (implying that ''n'' grows singly exponentially but at a higher rate than the Moore bound). Specifically, the construction of
Ramanujan graph In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders. AMurty's survey papernotes, Ramanu ...
s defined by satisfy the bound
:
This bound was improved slightly by .
It is unlikely that these graphs are themselves cages, but their existence gives an upper bound to the number of vertices needed in a cage.
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
External links
*
Brouwer, Andries E.br>
Cages* Royle, Gordon
an
*{{mathworld , title = Cage Graph , urlname = CageGraph
Graph families
Regular graphs