Cage (graph theory)

From Wikipedia, the free encyclopedia

The Tutte (3,8)-cage.
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.

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.

[edit] 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 Kr+1 on r+1 vertices, and the (r,4)-cage is a complete bipartite graph Kr,r on 2r vertices.

Other notable cages include the Moore graphs:

The known (3,g) cages, starting from g = 4, have numbers of vertices

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)

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
g: 3 4 5 6 7 8 9 10
r = 3: 4 6 10 14 24 30 58 70
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

[edit] 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. 
  • Tutte, W. T. (1947). "A family of cubical graphs.". Proc. Cambridge Philos. Soc. 43: 459–474. 

[edit] External links

  • Brouwer, Andries E. Cages