TOPICS
Search

Cage Graph


A (v,g)-cage graph is a v-regular graph of girth g having the minimum possible number of nodes. When v is not explicitly stated, the term "g-cage" generally refers to a (3,g)-cage.

A list of cage graphs can be obtained in the Wolfram Language using GraphData["Cage"].

There are a number of special cases (Wong 1982). The (2,g)-cage is the cycle graph C_g, the (v,2)-cage is the multigraph of v edges on two vertices, the (v,3)-cage is the complete graph K_(v+1), and the (v,4)-cage is the bipartite graph K_(v,v).

Let n(v,g) be the number of vertices in the (v,g)-cage graph. Then the following table summarizes exactly known values of n(v,g) for small values of g and v from 3 to 7. The value n(3,11)=112 was found by McKay et al. (1998).

gn(3,g)n(4,g)n(5,g)n(6,g)n(7,g)
SloaneA000066
345678
468101214
51019304050
61426426290
72467152294
83080170312
958275
1070384
11112
1212672827307812

Computing the number of n(v,g) vertices in a (v,g)-cage is very difficult for g>=5 and v>=3 (Wong 1982). A lower bound n_l(v,g)>=n(v,g) is given by

 n_l(v,g)={(v(v-1)^((g-1)/2)-2)/(v-2)   for g odd; (2(v-1)^(g/2)-2)/(v-2)   for g even
(1)

(Tutte 1967, p. 70; Bollobás 1978, p. 105; Wong 1982). For v=3, this gives the sequence of lower limits n_l(3,g) for g=1, 2, ... of 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, ... (OEIS A027383), which agrees with the actual values as far as they are known.

Sauer (1967ab) has obtained the best upper bounds known

n_u(3,g)={4/3+(29)/(12)2^(g-2) for g odd; 2/3+(29)/(12)2^(g-2) for g even
(2)
n_u(v,g)={2(v-1)^(g-2) for g odd; 4(v-1)^(g-3) for g even,
(3)

with v>=4 (Wong 1982).

The following table summarizes known cage graphs.

CageGraphs3

Cubic (v=3) cages were first discussed by Tutte (1947), but the intensive study of cage graphs did not begin until publication of an article by Erdős and Sachs (1963). There exists a (3,g)-cage for all g>=3, and the (3,g)-cages are unique for g=3 to 8. A selection of known (3,g)-cages are illustrated above (Read and Wilson 1998, pp. 271-272). The unique (3,8)-cage is the Tutte 8-cage (Read and Wilson 1998, p. 271). The first (3,9)-cage was found by Biggs and Hoare (1980), and Brinkmann et al. (1995) completed an exhaustive search yielding all 18 (3,9)-cages (Royle). One of them is illustrated by Holton and Sheehan (1993, p. 197). The three (3,10)-cages were found by O'Keefe and Wong (1980; Read and Wilson 1998, p. 272). Computations by McKay and W. Myrvold have demonstrated that a (3,11)-cage must have 112 vertices (McKay et al. 1998, Royle), and the single known example was found by Balaban (1973) and is sometimes known as the Balaban 10-cage. Myrvold and McKay subsequently proved that the minimal graph on 112 vertices is unique (B. D. McKay, pers. comm., May 20, 2003). The number of nonisomorphic (3,g) cages for g=3, 4, ... are given by 1, 1, 1, 1, 1, 1, 18, 3, 1, 1, ... (OEIS A052453; Gould 1988, Royle).

CageGraphs4

The known (4,g)-cages are illustrated above (Wong 1982). In March 2007, Exoo et al. conclusively identified one (4,7)-cage.

CageGraphs5

Some (5,g)-cages are shown above (Wong 1982). Meringer (1999) showed that there are four (5,5)-cages, despite the fact that Wong (1982) had indicated that only three such cages existed.

The Hoffman-Singleton graph is a (7,5)-cage.

Cage graphs for which the lower bound of equation (1) gives the actual number of vertices are known as Moore graphs.


See also

Balaban 10-Cage, Cayley Graph, Cubic Graph, Excess, Foster Cage, Harries Graph, Harries-Wong Graph, Heawood Graph, Hoffman-Singleton Graph, McGee Graph, Meringer Graph, Moore Graph, Petersen Graph, Regular Graph, Robertson Graph, Robertson-Wegner Graph, Tutte 8-Cage, Wong Graph

Explore with Wolfram|Alpha

References

Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships among the Cages." Rev. Roumaine Math. Pures Appl. 18, 1033-1043, 1973.Biggs, N. L. Ch. 23 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Biggs, N. L. "Constructions for Cubic Graphs of Large Girth." LSE Tech Report 97-11.Biggs, N. L. and Hoare, M. J. "A Trivalent Graph with 58 Vertices and Girth 9." Disc. Math. 30, 299-301, 1980.Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236-239, 1976.Brinkmann, G.; McKay, B. D.; and Saager, C. "The Smallest Cubic Graphs of Girth Nine." Combin., Probability, and Computing 5, 1-13, 1995.Brouwer, A. E. "Cages." http://www.win.tue.nl/~aeb/graphs/cages/cages.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Cages." §6.9 in Distance Regular Graphs. New York: Springer-Verlag, 1989.Erdős, P. and Sachs, H. "Reguläre graphen gegebener Taillenweite mit minimaler Knotenzahl." Wiss. Z. Uni. Halle (Math. Nat.) 12, 251-257, 1963.Exoo, G.; McKay, B.; and Myrvold, W. "A (4,7)-Cage." Preprint. March 2007. http://isu.indstate.edu/ge/CAGES/g4.7.67.Exoo, G. and Jajcay, R. "Dynamic Cage Survey." Electr. J. Combin. 15, 2008.Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 174-175, 1994.Holton, D. A. and Sheehan, J. Ch. 6 in The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.McKay, B. D.; Myrvold, W.; and Nadon, J. "Fast Backtracking Principles Applied to Find New Cages." 9th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1998. pp. 188-191.Meringer, M. "Fast Generation of Regular Graphs and Construction of Cages." J. Graph Th. 30, 137-146, 1999.O'Keefe, M. and Wong, P. K. "A Smallest Graph of Girth 10 and Valency 3." J. Combin. Th. B 29, 91-105, 1980.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: Papers in Applied Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Polster, B. A Geometrical Picture Book. New York: Springer-Verlag, p. 179, 1998.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 271-274, 1998.Royle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.Royle, G. "Cages of Higher Valency." http://school.maths.uwa.edu.au/~gordon/remote/cages/allcages.html.Sauer, N. "Extremaleigneschaften regulärer Graphen gegebener Taillenweite, I." Österreich. Akad. Wiss. Math. Natur. Kl. S.-B. II 176, 9-25, 1967a.Sauer, N. "Extremaleigneschaften regulärer Graphen gegebener Taillenweite, II." Österreich. Akad. Wiss. Math. Natur. Kl. S.-B. II 176, 27-43, 1967b.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 191 and 221, 1990.Sloane, N. J. A. Sequences A000066/M1013, A027383, A037233, and A052453 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Family of Cubical Graphs." Proc. Cambridge Philos. Soc. 43, 459-474, 1947.Tutte, W. T. Connectivity in Graphs. Toronto, Canada: Toronto University Press, pp. 70-83, 1967.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

Referenced on Wolfram|Alpha

Cage Graph

Cite this as:

Weisstein, Eric W. "Cage Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CageGraph.html

Subject classifications