From Surf Wiki (app.surf) — the open knowledge base

Cage (graph theory)

Regular graph with fewest possible nodes for its girth

Summary

Regular graph with fewest possible nodes for its girth

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 (r, g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has a length of 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 :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 non-isomorphic (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 graph K**r+1 on r + 1 vertices, and the (r,4)-cage is a complete bipartite graph K**r,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
4	6	10	14	24	30
5	8	19	26	67	80
6	10	30	42		170
7	12	40	62		312
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 \le 2\log_{r-1} n + O(1). 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 singly exponentially but at a higher rate than the Moore bound). Specifically, the construction of Ramanujan graphs defined by satisfy the bound :g \ge \frac{4}{3}\log_{r-1} n + O(1).

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

{{citation
{{citation
{{citation | 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 | author1-link = Paul Erdős | author2-link = Alfréd Rényi | author3-link = Vera T. Sós | 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 | author1-link = Nora Hartsfield | author2-link = Gerhard Ringel | title-link = Pearls in Graph Theory
{{citation | title-link = The Petersen Graph
{{citation
{{citation
{{citation

Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

graph-families regular-graphs

Want to explore this topic further?

Ask Mako anything about Cage (graph theory) — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report