In the mathematical field of graph theory, the Balaban 10-cage or Balaban -cage is a 3-regular graph with 70 vertices and 105 edges named after Alexandru T. Balaban. Published in 1972,Alexandru T. Balaban, A trivalent graph of girth ten, Journal of Combinatorial Theory Series B 12 (1972), 1–5. It was the first 10-cage discovered but it is not unique.Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. The Generalized Balaban Configurations. Preprint. 2001.
The proof of minimality of the number of vertices was given by Mary R. O'Keefe and Pak Ken Wong.Mary R. O'Keefe and Pak Ken Wong, A smallest graph of girth 10 and valency 3, Journal of Combinatorial Theory Series B 29 (1980), 91–105. There are 2 other distinct -cages, the Harries graph and the Harries–Wong graph.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976. The Harries–Wong graph and Harries graph are also cospectral.
The Balaban 10-cage has chromatic number 2, chromatic index 3, diameter 6, girth 10 and is hamiltonian. It is also a 3-vertex-connected graph and 3-edge-connected. The book thickness is 3 and the queue number is 2.Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018
The characteristic polynomial of the Balaban 10-cage is
Gallery
See also Molecular graph Balaban 11-cage
References