The Tutte (3,8)-cage.

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Image File history File links Tutte_eight_cage. ... Image File history File links Tutte_eight_cage. ... Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ... Girth generally refers to the circumference of a cylindrical object, such as a tree trunk. ...

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. In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ...

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

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

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.

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. In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ...

Other notable cages include the Moore graphs:

• (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
• (7,5)-cage: The Hoffman–Singleton graph, 50 vertices

The known (3,g) cages, starting from g = 4, have numbers of vertices The Petersen graph Another drawing of the Petersen graph, with only two crossings Another drawing, with each edge the same length The Petersen graph is a small graph that serves as a useful example and counterexample in graph theory. ... The Heawood graph, of girth 6 In the mathematical field of graph theory, a Heawood graph is the 6-cage, the smallest cubic graph of girth 6. ...

4, 6, 10, 14, 24, 30, 58, 70, 112, 126 (sequence A000066 in OEIS).

The known (r,g) cages, for higher values of r, starting in each case from g = 4, are (sequence A054760 in OEIS) The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

r = 4: 5, 8, 19, 26, 67, 80, 275, 384

r = 5: 6, 10, 30, 42, 152, 170

r = 6: 7, 12, 40, 62, 294, 312

r = 7: 8, 14, 50, 90

In addition, several (r,12)-cages are known. Starting at r = 3, the number of vertices in these cages are

126, 728, 2730, 7812

References

• Biggs, Norman (1993). Algebraic Graph Theory, 2nd ed., Cambridge Mathematical Library, 180–190. ISBN 0-521-45897-8.

• Hartsfield, Nora; Ringel, Gerhard (1990). Pearls in Graph Theory: A Comprehensive Introduction. Academic Press, 77–81. ISBN 0-12-328552-6.

• D. A. Holton and J. Sheehan (1993). The Petersen Graph. Cambridge University Press, 183–213. ISBN 0-521-43594-3.

• Tutte, W. T. (1947). "A family of cubical graphs.". Proc. Cambridge Philos. Soc. 43: 459–474.

The headquarters of the Cambridge University Press, in Trumpington Street, Cambridge. ... William Thomas Tutte (May 14, 1917 - May 2, 2002) was a British codebreaker and mathematician. ...

External links

• Brouwer, Andries E. Cages

• Royle, Gordon. Cubic Cages and Higher valency cages

• Weisstein, Eric W., Cage Graph at MathWorld.