In the mathematical field of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.
Formally, an is defined to be a graph in which each vertex has exactly neighbors, and in which the shortest cycle has a length of 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 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 non-isomorphic , each with 70 vertices: the , the Harries graph and the Harries–Wong graph. But there is only one : the (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 Kr+1 on r + 1 vertices, and the (r,4)-cage is a complete bipartite graph Kr,r on 2r vertices.
Notable cages include: (3,5)-cage: the Petersen graph, 10 vertices (3,6)-cage: the Heawood graph, 14 vertices (3,7)-cage: the McGee graph, 24 vertices (3,8)-cage: the Tutte–Coxeter graph, 30 vertices (3,10)-cage: the Balaban 10-cage, 70 vertices (3,11)-cage: the Balaban 11-cage, 112 vertices (3,12)-cage: the Tutte 12-cage, 126 vertices (4,5)-cage: the Robertson graph, 19 vertices (7,5)-cage: The Hoffman–Singleton graph, 50 vertices. When r − 1 is a prime power, the (r,6) cages are the incidence graphs of projective planes. 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: 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
Asymptotics For large values of g, the Moore bound implies that the number n of vertices must grow at least 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 . The best known lower bounds on g are also logarithmic, but with a smaller constant factor (implying that n grows exponentially but at a higher rate than the Moore bound). Specifically, the construction of Ramanujan graphs 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. Cages Royle, Gordon. Cubic Cages and Higher valency cages