TOPICS
Search

Balaban 11-Cage


BalabanGraph11

The Balaban 11-cage is the unique 11-cage graph, derived via a tree excision from the 12-cage graph by Balaban (1973) and proven unique by McKay and Myrvold in 2003. It is implemented in the Wolfram Language as GraphData["Balaban11Cage"].

It has LCF notation [44, 26, -47, -15, 35, -39, 11, -27, 38, -37, 43, 14, 28, 51, -29, -16, 41, -11, -26, 15, 22, -51, -35, 36, 52, -14, -33, -26, -46, 52, 26, 16, 43, 33, -15, 17, -53, 23, -42, -35, -28, 30, -22, 45, -44, 16, -38, -16, 50, -55, 20, 28, -17, -43, 47, 34, -26, -41, 11, -36, -23, -16, 41, 17, -51, 26, -33, 47, 17, -11, -20, -30, 21, 29, 36, -43, -52, 10, 39, -28, -17, -52, 51, 26, 37, -17, 10, -10, -45, -34, 17, -26, 27, -21, 46, 53, -10, 29, -50, 35, 15, -47, -29, -41, 26, 33, 55, -17, 42, -26, -36, 16].

It has 112 vertices, 168 edges, girth 11 (by definition), and diameter 8. It has characteristic polynomial

 chi_G(x)=(x-3)x^(12)(x^2-2)^(12)(x^2-6)^5(-2-6x+x^2+x^3)×(2-4x-x^2+x^3)^2(4+4x-6x^2-x^3+x^4)^4(4+12x-6x^2-8x^3+x^4+x^5)^8

and chromatic number 3.

The order of its automorphism group is 64.

Balaban11CageMatrices

The plots above show the adjacency, incidence, and distance matrices of the graph.

No particularly nice embedding is known for the 11-cage. The Fifth Annual Graph Drawing Contest used the 11-cage as the basis of a graph drawing contest, but results were mixed (Eades et al. 1998).


See also

Balaban 10-Cage, Cage Graph

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha

References

Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math. 18, 1033-1043, 1973.Eades, P.; Marks, J.; Mutzel, P.; and North, S. "Graph-Drawing Contest Report." Oct. 1998. http://www.merl.com/papers/docs/TR98-16.pdf.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 272, 1998.Royle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

Cite this as:

Pegg, Ed Jr. and Weisstein, Eric W. "Balaban 11-Cage." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Balaban11-Cage.html

Subject classifications