Cage (graph theory)

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 : 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 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 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:

g
r
 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 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 (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 singly exponentially but at a higher rate than the Moore bound). Specifically, the Ramanujan graphs (Lubotzky, Phillips & Sarnak 1988) satisfy the bound

g\ge \frac{4}{3}\log_{r-1} n + O(1).

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

External links

This article is issued from Wikipedia - version of the Thursday, March 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.