Английская Википедия:Cage (graph theory)
Шаблон:Short description [[Image:Tutte eight cage.svg|thumb|right|The [[Tutte–Coxeter graph|Tutte Шаблон:Nowrap]].]]
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 Шаблон:Nowrap is defined to be a graph in which each vertex has exactly Шаблон:Mvar neighbors, and in which the shortest cycle has length exactly Шаблон:Mvar. An Шаблон:Nowrap is an Шаблон:Nowrap with the smallest possible number of vertices, among all Шаблон:Nowrap. A Шаблон:Nowrap is often called a Шаблон:Nowrap.
It is known that an Шаблон:Nowrap exists for any combination of Шаблон:Nowrap and Шаблон:Nowrap. It follows that all Шаблон:Nowrap exist.
If a Moore graph exists with degree Шаблон:Mvar and girth Шаблон:Mvar, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth Шаблон:Mvar must have at least
- <math>1+r\sum_{i=0}^{(g-3)/2}(r-1)^i</math>
vertices, and any cage with even girth Шаблон:Mvar must have at least
- <math>2\sum_{i=0}^{(g-2)/2}(r-1)^i</math>
vertices. Any Шаблон:Nowrap 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 Шаблон:Mvar and Шаблон:Mvar. For instance there are three nonisomorphic Шаблон:Nowrap, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries–Wong graph. But there is only one Шаблон:Nowrap: 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 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
- (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:
| Шаблон:Diagonal split header | 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 singly exponentially as a function of g. Equivalently, g can be at most proportional to the logarithm of n. More precisely,
- <math>g\le 2\log_{r-1} n + O(1).</math>
It is believed that this bound is tight or close to tight Шаблон:Harv. 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 Шаблон:Harvtxt satisfy the bound
- <math>g\ge \frac{4}{3}\log_{r-1} n + O(1).</math>
This bound was improved slightly by Шаблон:Harvtxt.
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
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
External links
- Brouwer, Andries E. Cages
- Royle, Gordon. Cubic Cages and Higher valency cages
- Шаблон:Mathworld
