Cage (graph theory)

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.

The Tutte (3,8)-cage.

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. It is known that an (r,g)-graph exists for any combination of r ≥ 2 and g ≥ 3. An (r,g)-cage is an (r,g)-graph with the fewest possible number of vertices, among all (r,g)-graphs.

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

1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}

vertices, and any cage with even girth g must have at least

2\sum _{i=0}^{(g-2)/2}(r-1)^{i}

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 degree-one graph has no cycle, and a connected degree-two 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 K_r+1 on r+1 vertices, and the (r,4)-cage is a complete bipartite graph K_r,r on 2r vertices.

Other notable cages include:

(3,5)-cage: the Petersen graph, 10 vertices
(3,6)-cage: the Heawood graph, 14 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:

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

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,

g\leq 2\log _{r-1}n+O(1).

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

g\geq {\frac {4}{3}}\log _{r-1}n+O(1).

This bound was improved slightly by Lazebnik, Ustimenko & Woldar (1995).

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

Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge Mathematical Library, pp. 180–190, ISBN 0-521-45897-8.
Bollobás, Béla; Szemerédi, Endre (2002), "Girth of sparse graphs", Journal of Graph Theory, 39 (3): 194–200, doi:10.1002/jgt.10023, MR 1883596.
Exoo, G; Jajcay, R (2008), "Dynamic Cage Survey", Dynamic Surveys, Electronic Journal of Combinatorics, DS16, archived from the original on 2015-01-01, retrieved 2012-03-25.
Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235, archived from the original (PDF) on 2016-03-09, retrieved 2010-02-23.
Hartsfield, Nora; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, pp. 77–81, ISBN 0-12-328552-6.
Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, pp. 183–213, ISBN 0-521-43594-3.
Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J. (1995), "A new series of dense graphs of high girth", Bulletin of the American Mathematical Society, New Series, 32 (1): 73–79, arXiv:math/9501231, doi:10.1090/S0273-0979-1995-00569-0, MR 1284775.
Lubotzky, A.; Phillips, R.; Sarnak, P. (1988), "Ramanujan graphs", Combinatorica, 8 (3): 261–277, doi:10.1007/BF02126799, MR 0963118.
Tutte, W. T. (1947), "A family of cubical graphs", Proc. Cambridge Philos. Soc., 43 (4): 459–474, Bibcode:1947PCPS...43..459T, doi:10.1017/S0305004100023720.

External links

Brouwer, Andries E. Cages
Royle, Gordon. Cubic Cages and Higher valency cages
Weisstein, Eric W. "Cage Graph". MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.