Balaban 10-cage

Balaban 10-cage
Balaban 10-cage
	The Balaban 10-cage
Named after	Alexandru T. Balaban
Vertices	70
Edges	105
Radius	6
Diameter	6
Girth	10
Automorphisms	80
Chromatic number	2
Chromatic index	3
Genus	9
Book thickness	3
Queue number	2
Properties	Cubic; Cage; Hamiltonian
	Table of graphs and parameters

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

In the mathematical field of graph theory, the Balaban 10-cage or Balaban $(3,10)$ -cage is a 3-regular graph with 70 vertices and 105 edges named after Alexandru T. Balaban.^[1] Published in 1972,^[2] It was the first 10-cage discovered but it is not unique.^[3]

The complete list of 10-cages and the proof of minimality was given by Mary R. O'Keefe and Pak Ken Wong.^[4] There exist 3 distinct $(3,10)$ -cages, the other two being the Harries graph and the Harries–Wong graph.^[5] Moreover, the Harries–Wong graph and Harries graph are cospectral graphs.

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.^[6]

The characteristic polynomial of the Balaban 10-cage is

(x-3)(x-2)(x-1)^{8}x^{2}(x+1)^{8}(x+2)(x+3)\cdot

\cdot (x^{2}-6)^{2}(x^{2}-5)^{4}(x^{2}-2)^{2}(x^{4}-6x^{2}+3)^{8}.

Gallery

The chromatic number of the Balaban 10-cage is 2.
The chromatic index of the Balaban 10-cage is 3.
Another drawing of the Balaban 10-cage.

References

^ Weisstein, Eric W. "Balaban 10-Cage". MathWorld.
^ Alexandru T. Balaban, A trivalent graph of girth ten, Journal of Combinatorial Theory Series B 12 (1972), 1–5.
^ Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. [1].
^ 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.
^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.
^ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018

[1] Weisstein, Eric W. "Balaban 10-Cage". MathWorld.

[2] Alexandru T. Balaban, A trivalent graph of girth ten, Journal of Combinatorial Theory Series B 12 (1972), 1–5.

[3] Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. [1].

[4] 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.

[5] Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.

[6] Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018

[1]

[2]

[3]

[4]

[5]

[6]

Gallery

See also

References