{{Short description|Regular graph with fewest possible nodes for its girth}} {{Dark mode invert|[[Image:Tutte eight cage.svg|thumb|right|The Tutte {{nowrap|{{math|(3,8)}}-cage}}.]]}}
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|{{math|(''r'', ''g'')}}-graph}} is defined to be a graph in which each vertex has exactly {{mvar|r}} neighbors, and in which the shortest cycle has a length of exactly {{mvar|g}}. An {{nowrap|{{math|(''r'', ''g'')}}-cage}} is an {{nowrap|{{math|(''r'', ''g'')}}-graph}} with the smallest possible number of vertices, among all {{nowrap|{{math|(''r'', ''g'')}}-graphs}}. A {{nowrap|{{math|(3, ''g'')}}-cage}} is often called a {{nowrap|{{mvar|g}}-cage}}.
It is known that an {{nowrap|{{math|(''r'', ''g'')}}-graph}} exists for any combination of {{nowrap|{{math|''r'' ≥ 2}}}} and {{nowrap|{{math|''g'' ≥ 3}}}}. It follows that all {{nowrap|{{math|(''r'', ''g'')}}-cages}} exist.
If a Moore graph exists with degree {{mvar|r}} and girth {{mvar|g}}, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth {{mvar|g}} 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|g}} must have at least :<math>2\sum_{i=0}^{(g-2)/2}(r-1)^i</math> vertices. Any {{nowrap|{{math|(''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 {{mvar|r}} and {{mvar|g}}. For instance there are three non-isomorphic {{nowrap|{{math|(3, 10)}}-cages}}, each with 70 vertices: the {{nowrap|Balaban 10-cage}}, the Harries graph and the Harries–Wong graph. But there is only one {{nowrap|{{math|(3, 11)}}-cage}}: the {{nowrap|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 ''K''<sub>''r''+1</sub> on ''r'' + 1 vertices, and the (''r'',4)-cage is a complete bipartite graph ''K''<sub>''r'',''r''</sub> on 2''r'' 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: {| class="wikitable" ! {{diagonal split header|r|g}} || 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, :<math>g \le 2\log_{r-1} n + O(1).</math> It is believed that this bound is tight or close to tight {{harv|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 exponentially but at a higher rate than the Moore bound). Specifically, the construction of Ramanujan graphs defined by {{harvtxt|Lubotzky|Phillips|Sarnak|1988}} satisfy the bound :<math>g \ge \frac{4}{3}\log_{r-1} n + O(1).</math>
This bound was improved slightly by {{harvtxt|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 == *{{citation | last = Biggs | first = Norman | authorlink = Norman L. Biggs | edition = 2nd | isbn = 0-521-45897-8 | pages = 180–190 | publisher = Cambridge Mathematical Library | title = Algebraic Graph Theory | year = 1993}}. *{{citation | last1 = Bollobás | first1 = Béla | author1-link = Béla Bollobás | last2 = Szemerédi | first2 = Endre | author2-link = Endre Szemerédi | doi = 10.1002/jgt.10023 | issue = 3 | journal = Journal of Graph Theory | mr = 1883596 | pages = 194–200 | title = Girth of sparse graphs | volume = 39 | year = 2002| doi-access = free }}. *{{citation | last1 = Exoo | first1 = G | last2 = Jajcay | first2 = R | journal = Electronic Journal of Combinatorics | department = Dynamic Surveys | title = Dynamic Cage Survey | url = http://www.combinatorics.org/ojs/index.php/eljc/article/download/ds16/pdf | volume = DS16 | year = 2008 | access-date = 2012-03-25 | archive-url = https://web.archive.org/web/20150101225435/http://www.combinatorics.org/ojs/index.php/eljc/article/download/DS16/pdf | archive-date = 2015-01-01 | url-status = dead }}. *{{citation | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős | last2 = Rényi | first2 = Alfréd | author2-link = Alfréd Rényi | last3 = Sós | first3 = Vera T. | author3-link = Vera T. Sós | journal = Studia Sci. Math. Hungar. | pages = 215–235 | title = On a problem of graph theory | url = http://www.math-inst.hu/~p_erdos/1966-06.pdf | volume = 1 | year = 1966 | access-date = 2010-02-23 | archive-url = https://web.archive.org/web/20160309214909/http://www.math-inst.hu/~p_erdos/1966-06.pdf | archive-date = 2016-03-09 | url-status = dead }}. *{{citation | last1 = Hartsfield | first1 = Nora | author1-link = Nora Hartsfield | last2 = Ringel | first2 = Gerhard | author2-link = Gerhard Ringel | isbn = 0-12-328552-6 | pages = [https://archive.org/details/pearlsingraphthe00har_f6p/page/77 77–81] | publisher = Academic Press | title = Pearls in Graph Theory: A Comprehensive Introduction | year = 1990 | title-link = Pearls in Graph Theory }}. *{{citation | last1 = Holton | first1 = D. A. | last2 = Sheehan | first2 = J. | isbn = 0-521-43594-3 | pages = 183–213 | publisher = Cambridge University Press | title = The Petersen Graph | title-link = The Petersen Graph | year = 1993}}. *{{citation | last1 = Lazebnik | first1 = F. | last2 = Ustimenko | first2 = V. A. | last3 = Woldar | first3 = A. J. | doi = 10.1090/S0273-0979-1995-00569-0 | issue = 1 | journal = Bulletin of the American Mathematical Society | mr = 1284775 | pages = 73–79 | title = A new series of dense graphs of high girth | volume = 32 | year = 1995| arxiv = math/9501231}}. *{{citation | last1 = Lubotzky | first1 = A. | author1-link = Alexander Lubotzky | last2 = Phillips | first2 = R. | last3 = Sarnak | first3 = P. | author3-link = Peter Sarnak | doi = 10.1007/BF02126799 | issue = 3 | journal = Combinatorica | mr = 963118 | pages = 261–277 | title = Ramanujan graphs | volume = 8 | year = 1988}}. *{{citation | last = Tutte | first = W. T. | author-link = William Thomas Tutte | doi = 10.1017/S0305004100023720 | issue = 4 | journal = Proc. Cambridge Philos. Soc. | pages = 459–474 | title = A family of cubical graphs | volume = 43 | year = 1947| bibcode = 1947PCPS...43..459T}}.
== External links ==
* Brouwer, Andries E. [https://web.archive.org/web/20081227233341/http://www.win.tue.nl/~aeb/drg/graphs/cages/cages.html Cages] * Royle, Gordon. [https://web.archive.org/web/20120730080521/http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/index.html Cubic Cages] and [https://web.archive.org/web/20120802034729/http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/allcages.html Higher valency cages] *{{mathworld | title = Cage Graph | urlname = CageGraph}}
Category:Graph families Category:Regular graphs