Cage (graph theory)

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.

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+rsum_{i=0}^{(g-3)/2}(r-1)^ivertices, and any cage with even girth "g" must have at least:2sum_{i=0}^{(g-2)/2}(r-1)^ivertices. 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 2"r" vertices.

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:4, 6, 10, 14, 24, 30, 58, 70, 112, 126 OEIS|id=A000066.

The known ("r","g") cages, for higher values of "r", starting in each case from "g" = 4, are OEIS|id=A054760:"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

*cite book
author = Biggs, Norman
title = Algebraic Graph Theory
edition = 2nd ed.
publisher = Cambridge Mathematical Library
pages = 180–190
year = 1993
id = ISBN 0-521-45897-8

*cite book
author = Hartsfield, Nora; Ringel, Gerhard
title = Pearls in Graph Theory: A Comprehensive Introduction
publisher = Academic Press
id = ISBN 0-12-328552-6
year = 1990
pages = 77–81

* cite book
author=D. A. Holton and J. Sheehan
title=The Petersen Graph
publisher=Cambridge University Press
year=1993
id=ISBN 0-521-43594-3
pages=183–213

*cite journal
author = Tutte, W. T.
authorlink = William Thomas Tutte
title = A family of cubical graphs.
journal = Proc. Cambridge Philos. Soc.
volume = 43
year = 1947
pages = 459–474

External links

* Brouwer, Andries E. [http://www.win.tue.nl/~aeb/drg/graphs/cages/cages.html Cages]

* Royle, Gordon. [http://www.csse.uwa.edu.au/~gordon/cages/ Cubic Cages] and [http://www.csse.uwa.edu.au/~gordon/cages/allcages.html Higher valency cages]

*mathworld | title = Cage Graph | urlname = CageGraph


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Girth (graph theory) — In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.[1] If the graph does not contain any cycles (i.e. it s an acyclic graph), its girth is defined to be infinity.[2] For example, a 4 cycle (square) has… …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • Cage — may refer to:Fiction* Cage (film) , a 1989 film starring Lou Ferrigno * , an episode of Law Order: Special Victims Unit * John Cage (character), a fictional character in the television show Ally McBeal * Johnny Cage, a fictional character from… …   Wikipedia

  • McGee graph — The McGee Graph Named after W. F. McGee Vertices 24 Edges …   Wikipedia

  • Moore graph — Unsolved problems in mathematics Does a Moore graph with girth 5 and degree 57 exist? In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound An equivalent definition of a Moore …   Wikipedia

  • 10-cage de Balaban — Représentation de la 10 cage de Balaban Nombre de sommets 70 Nombre d arêtes 105 Rayon 6 Diamètre 6 …   Wikipédia en Français

  • Cubic graph — Not to be confused with graphs of cubic functions. The Petersen graph is a Cubic graph …   Wikipedia

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia

  • Distance-transitive graph — The Biggs Smith graph, the largest 3 regular distance transitive graph. Graph families defined by their automorphisms distance transitive …   Wikipedia

  • Tutte–Coxeter graph — infobox graph name = Tutte–Coxeter graph image caption = namesake = W. T. Tutte H. S. M. Coxeter vertices = 30 edges = 45 girth = 8 chromatic number = 2 chromatic index = properties = Cubic Cage Moore graph Arc transitiveIn the mathematical field …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”