TOPICS
Search

Cage Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A cage graph of type (v,g), where v>=2 and g>=3 are integers, is a finite simple connected graph that is a v-regular graph with girth g and the minimum possible number of vertices. When v is not explicitly stated, the term "g-cage" generally refers to a (3,g)-cage.

A regular girth graph, or (v,g)-graph, has the specified degree and girth without the minimality requirement. A smallest known example gives an upper bound on the order of a cage, but is a cage only when its minimality has been established.

Individual cage graphs are implemented in the Wolfram Language as GraphData[{"Cage", {v, g}}]. When several cages are stored for the same parameters, an additional index identifies a particular cage using GraphData[{"Cage", {v, g, i}}]. A list of available cage graphs is given by GraphData["Cage"].

Examples of regular girth graphs, including some whose minimality is unproved, will be implemented in a future version of the Wolfram Language as GraphData[{"RegularGirth", {d, g, n}}], where d, g, and n specify the degree, girth, and order, respectively.

There are a number of special cases (Wong 1982). The (2,g)-cage is the cycle graph C_g, the (v,3)-cage is the complete graph K_(v+1), and the (v,4)-cage is the complete bipartite graph K_(v,v). If the definition is extended to multigraphs and g=2, then the (v,2)-cage has v parallel edges on two vertices.

Let n(v,g) be the minimum vertex count of a (v,g)-cage. 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)
SloaneA000066A037233
345678
468101214
51019304050
61426426290
72467
83080170312
958
1070
11112
1212672827307812

Determining the minimum vertex count n(v,g) of a (v,g)-cage is very difficult for g>=5 and v>=3 (Wong 1982). For v>=3 and g>=3, 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 bounds n_l(3,g) for g=3, 4, ... of 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, ... (OEIS A027383). The lower bound is not always attained. For example, n_l(3,7)=22 while n(3,7)=24.

Sauer (1967ab) obtained the general upper bounds

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).

For odd g>=7 and v>=3, the Moore bound is not attained (Damerell 1973). A regular graph of odd girth g>=5 cannot have vertex count n_l(v,g)+1 (Bannai and Ito 1981). Therefore n(v,g)>=n_l(v,g)+2 for odd g>=7 and v>=3.

For some pairs (v,g), the order of a (v,g)-cage is not exactly known. The following table gives known bounds for the corresponding cage orders.

(v,g)bounds for n(v,g)references
(3,13)[202,272]Biggs (1998), McKay et al. (1998)
(3,14)[262,384]Exoo (2002), de la Cruz and Pizaña (2026)
(3,15)[388,620]Biggs and Hoare (1983), de la Cruz and Pizaña (2026)
(3,16)[512,936]Exoo et al. (2026)
(3,17)[770,2048]Exoo et al. (2026), de la Cruz and Pizaña (2026)
(4,9)[165,270]Exoo et al. (2026), de la Cruz and Pizaña (2026)
(4,10)[245,320]Exoo and Jajcay (2011), Exoo et al. (2026)
(4,11)[487,713]Damerell (1973), Bannai and Ito (1981), Exoo et al. (2026)
(5,7)[110,152]Exoo and Jajcay (2011), de la Cruz and Pizaña (2026)
(5,9)[428,1116]Exoo et al. (2026)
(6,7)[189,294]Exoo and Jajcay (2011)
(6,11)[4689,7783]Damerell (1973), Bannai and Ito (1981), Exoo et al. (2026)
(8,7)[459,774]Damerell (1973), Bannai and Ito (1981), Exoo et al. (2026)
(9,5)[86,96]Jørgensen (2005), Exoo and Jajcay (2011)
(10,5)[103,124]Exoo and Jajcay (2011), House of Graphs
(10,7)[913,1608]Damerell (1973), Bannai and Ito (1981), Exoo et al. (2026)
(11,5)[124,154]Exoo and Jajcay (2011), House of Graphs
(11,6)[224,240]Wong (1982), Exoo and Jajcay (2011)
(12,5)[147,203]Exoo and Jajcay (2011)
(12,7)[1599,2890]Damerell (1973), Bannai and Ito (1981), Exoo et al. (2026)
(13,5)[174,226]Exoo and Jajcay (2011), House of Graphs
(14,5)[199,280]Exoo and Jajcay (2011), House of Graphs
(14,7)[2565,4716]Damerell (1973), Bannai and Ito (1981), Exoo et al. (2026)

The reference column cites primary sources when they are available, and otherwise uses the survey of Exoo and Jajcay (2011) or House of Graphs for tabulated bounds. See also the online tabulations of Brouwer and Royle.

The following table summarizes known cage graphs.

(v,g)countsnamed cages (or references)
(3,3)1complete graph K_4
(3,4)1complete bipartite graph K_(3,3)
(3,5)1Petersen graph P
(3,6)1Heawood graph
(3,7)1McGee graph
(3,8)1Tutte 8-cage
(3,9)18Biggs and Hoare (1980), Brinkmann et al. (1995)
(3,10)3Balaban 10-cage, Harries graph, Harries-Wong graph
(3,11)1Balaban 11-cage; Balaban (1973), Exoo et al. (2011)
(3,12)1Tutte 12-cage; Polster (1998, p. 179)
(4,3)1pentatope graph K_5
(4,4)1complete bipartite graph K_(4,4)
(4,5)1Robertson graph
(4,6)1Wong (1982)
(4,7)>=1Exoo (2007)
(4,8)>=1Royle
(4,12)>=1generalized dodecagon GD(1,3)
(5,3)1complete graph K_6
(5,4)1complete bipartite graph K_(5,5)
(5,5)4Wong graph, Foster cage, Meringer graph, Robertson-Wegner graph
(5,6)>=1Royle
(5,8)>=1Royle
(5,12)>=1Royle
(6,3)1complete graph K_7
(6,4)1complete bipartite graph K_(6,6)
(6,8)>=1Royle
(6,12)>=1Royle
(7,3)1complete graph K_8
(7,4)1complete bipartite graph K_(7,7)
(7,5)1Hoffman-Singleton graph
(8,8)>=1Royle
(9,8)>=1Royle
(10,8)>=1Royle
(12,8)>=1Royle
(14,6)>=1Royle
(14,8)>=1Royle
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 first (3,10)-cage was found by Balaban (1972), and the other two were found by O'Keefe and Wong (1980). 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 known as the Balaban 11-cage. Uniqueness of the (3,11)-cage was established by exhaustive search (Exoo et al. 2011). 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). Exoo et al. (2011) established n(4,7)=67 by exhaustive search and constructed 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.

For v>2, cage graphs for which the Moore bound in equation (1) gives the actual number of vertices are known as Moore graphs.

See also

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

Explore with Wolfram|Alpha

References

Balaban, A. T. "A Trivalent Graph of Girth Ten." J. Combin. Th. B 12, 1-5, 1972. https://doi.org/10.1016/0095-8956(72)90028-7.Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships among the Cages." Rev. Roumaine Math. Pures Appl. 18, 1033-1043, 1973.Bannai, E. and Ito, T. "Regular Graphs with Excess One." Disc. Math. 37, 147-158, 1981. https://doi.org/10.1016/0012-365X(81)90215-6.Biggs, N. L. "Constructions for Cubic Graphs with Large Girth." Elec. J. Combin. 5, A1, 1998. https://doi.org/10.37236/1386.Biggs, N. L. Ch. 23 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Biggs, N. L. and Hoare, M. J. "A Trivalent Graph with 58 Vertices and Girth 9." Disc. Math. 30, 299-301, 1980.Biggs, N. L. and Hoare, M. J. "The Sextet Construction for Cubic Graphs." Combinatorica 3, 153-165, 1983.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 4, 317-329, 1995. https://doi.org/10.1017/S0963548300001693.Brouwer, A. E. "Cages." https://aeb.win.tue.nl/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.Damerell, R. M. "On Moore Graphs." Proc. Cambridge Philos. Soc. 74, 227-236, 1973. https://doi.org/10.1017/S0305004100048015.de la Cruz, C. M. and Pizaña, M. A. "On Cages and Choosing with Symmetries." Elec. J. Combin. 33, P1.54, 2026. https://doi.org/10.37236/14471.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. "A Small Trivalent Graph of Girth 14." Elec. J. Combin. 9, No. 1, N3, 2002. https://doi.org/10.37236/1664.Exoo, G.; Goedgebeur, J.; Jooken, J.; Stubbe, L.; and van den Eede, T. "New Small Regular Graphs of Given Girth: The Cage Problem and Beyond." Elec. J. Combin. 33, P3.48, 2026. https://doi.org/10.37236/14834.Exoo, G. and Jajcay, R. "Dynamic Cage Survey." Elec. J. Combin., Dynamic Survey DS16, 2011. https://doi.org/10.37236/37.Exoo, G.; McKay, B. D.; Myrvold, W.; and Nadon, J. "Computational Determination of (3,11) and (4,7) Cages." J. Discrete Algorithms 9, 166-169, 2011. https://doi.org/10.1016/j.jda.2010.11.001.Exoo, G.; McKay, B.; and Myrvold, W. "A (4,7)-Cage." https://isu.indstate.edu/~gexoo/CAGES/g4.7.67.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.House of Graphs. "Cages." https://houseofgraphs.org/meta-directory/cages.Jørgensen, L. K. "Girth 5 Graphs from Relative Difference Sets." Disc. Math. 293, 177-184, 2005. https://doi.org/10.1016/j.disc.2004.08.029.McKay, B. D.; Myrvold, W.; and Nadon, J. "Fast Backtracking Principles Applied to Find New Cages." In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, January 1998. New York: ACM, pp. 188-191, 1998.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." https://web.archive.org/web/20060823134140/http://people.csse.uwa.edu.au/gordon/cages/index.html.Royle, G. "Cages of Higher Valency." https://web.archive.org/web/20090125032457/http://people.csse.uwa.edu.au/gordon/cages/allcages.html.Sauer, N. "Extremaleigenschaften regulärer Graphen gegebener Taillenweite, I." Österreich. Akad. Wiss. Math. Natur. Kl. S.-B. II 176, 9-25, 1967a.Sauer, N. "Extremaleigenschaften 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 Resource. https://mathworld.wolfram.com/CageGraph.html

Subject classifications