Formally, an (r, g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g.
An (r, g)-cage is an (r, g)-graph with the smallest possible number of vertices, among all (r, g)-graphs. A (3, g)-cage is often called a g-cage.
It is known that an (r, g)-graph exists for any combination of r ≥ 2 and g ≥ 3. It follows that all (r, g)-cages exist.
If a Moore graph exists with degree r and girth g, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth g must have at least
vertices, and any cage with even girth g must have at least
vertices. Any (r, g)-graph 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 r and g. For instance there are three nonisomorphic (3, 10)-cages, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries–Wong graph. But there is only one (3, 11)-cage: 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 graphKr+1 on r+1 vertices, and the (r,4)-cage is a complete bipartite graphKr,r on 2r vertices.
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:
More information gr ...
g
r
3
4
5
6
7
8
9
10
11
12
3
4
6
10
14
24
30
58
70
112
126
4
5
8
19
26
67
80
728
5
6
10
30
42
170
2730
6
7
12
40
62
312
7812
7
8
14
50
90
Close
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 of n. More precisely,
It is believed that this bound is tight or close to tight (Bollobás & Szemerédi 2002). 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 graphs defined by Lubotzky, Phillips & Sarnak (1988) satisfy the bound
This article uses material from the Wikipedia article Cage_(graph_theory), and is written by contributors.
Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.