A -cage graph is a -regular graph of girth having the minimum possible number of nodes. When is not explicitly stated, the term "-cage" generally refers to a -cage.
A list of cage graphs can be obtained in the Wolfram Language using GraphData["Cage"].
There are a number of special cases (Wong 1982). The -cage is the cycle graph , the -cage is the multigraph of edges on two vertices, the -cage is the complete graph , and the -cage is the bipartite graph .
Let be the number of vertices in the -cage graph. Then the following table summarizes exactly known values of for small values of and from 3 to 7. The value was found by McKay et al. (1998).
Sloane | A000066 | ||||
3 | 4 | 5 | 6 | 7 | 8 |
4 | 6 | 8 | 10 | 12 | 14 |
5 | 10 | 19 | 30 | 40 | 50 |
6 | 14 | 26 | 42 | 62 | 90 |
7 | 24 | 67 | 152 | 294 | |
8 | 30 | 80 | 170 | 312 | |
9 | 58 | 275 | |||
10 | 70 | 384 | |||
11 | 112 | ||||
12 | 126 | 728 | 2730 | 7812 |
Computing the number of vertices in a -cage is very difficult for and (Wong 1982). A lower bound is given by
(1)
|
(Tutte 1967, p. 70; Bollobás 1978, p. 105; Wong 1982). For , this gives the sequence of lower limits for , 2, ... of 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, ... (OEIS A027383), which agrees with the actual values as far as they are known.
Sauer (1967ab) has obtained the best upper bounds known
(2)
| |||
(3)
|
with (Wong 1982).
The following table summarizes known cage graphs.
counts | named cages (or references) | |
1 | complete graph | |
1 | complete bipartite graph | |
1 | Petersen graph | |
1 | Heawood graph | |
1 | McGee graph | |
1 | Tutte 8-cage | |
18 | Biggs and Hoare (1980), Brinkmann et al. (1995) | |
3 | Balaban 10-cage, Harries graph, Harries-Wong graph | |
1 | Balaban 11-cage; Balaban (1973), Myrvold and McKay | |
1 | Tutte 12-cage; Polster et al. (1998, p. 179) | |
1 | complete graph | |
1 | complete bipartite graph | |
1 | Robertson graph | |
1 | Wong (1982) | |
Exoo (2007) | ||
Royle | ||
generalized dodecagon | ||
1 | complete graph | |
1 | complete bipartite graph | |
4 | Wong graph, Foster cage, Meringer graph, Robertson-Wegner graph | |
Royle | ||
Royle | ||
Royle | ||
Royle | ||
1 | complete graph | |
1 | complete bipartite graph | |
Royle | ||
Royle | ||
Royle | ||
1 | complete graph | |
1 | complete bipartite graph | |
1 | Hoffman-Singleton graph | |
Royle | ||
Royle | ||
Royle | ||
Royle | ||
Royle | ||
Royle |
Cubic () cages were first discussed by Tutte (1947), but the intensive study of cage graphs did not begin until publication of an article by Erdős and Sachs (1963). There exists a -cage for all , and the -cages are unique for to 8. A selection of known -cages are illustrated above (Read and Wilson 1998, pp. 271-272). The unique -cage is the Tutte 8-cage (Read and Wilson 1998, p. 271). The first -cage was found by Biggs and Hoare (1980), and Brinkmann et al. (1995) completed an exhaustive search yielding all 18 -cages (Royle). One of them is illustrated by Holton and Sheehan (1993, p. 197). The three -cages were found by O'Keefe and Wong (1980; Read and Wilson 1998, p. 272). Computations by McKay and W. Myrvold have demonstrated that a -cage must have 112 vertices (McKay et al. 1998, Royle), and the single known example was found by Balaban (1973) and is sometimes known as the Balaban 10-cage. Myrvold and McKay subsequently proved that the minimal graph on 112 vertices is unique (B. D. McKay, pers. comm., May 20, 2003). The number of nonisomorphic cages for , 4, ... are given by 1, 1, 1, 1, 1, 1, 18, 3, 1, 1, ... (OEIS A052453; Gould 1988, Royle).
The known -cages are illustrated above (Wong 1982). In March 2007, Exoo et al. conclusively identified one -cage.
Some -cages are shown above (Wong 1982). Meringer (1999) showed that there are four -cages, despite the fact that Wong (1982) had indicated that only three such cages existed.
The Hoffman-Singleton graph is a -cage.
Cage graphs for which the lower bound of equation (1) gives the actual number of vertices are known as Moore graphs.