Balaban 10-cage

{{Short description|Cubic graph with 70 nodes and 105 edges}}

{{infobox graph

| name = Balaban 10-cage

| image = 220px

| image_caption = The Balaban 10-cage

| namesake = Alexandru T. Balaban

| vertices = 70

| edges = 105

| automorphisms = 80

| girth = 10

| diameter = 6

| radius = 6

| chromatic_number = 2

| chromatic_index = 3

| book_thickness = 3

| queue_number = 2

| genus = 9

| properties = Cubic
Cage
Hamiltonian

|book thickness=3|queue number=2}}

In the mathematical field of graph theory, the Balaban 10-cage or Balaban {{math|(3,10)}}-cage is a 3-regular graph with 70 vertices and 105 edges named after Alexandru T. Balaban.{{MathWorld|urlname=Balaban10-Cage|title=Balaban 10-Cage}} 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. [http://citeseer.ist.psu.edu/448980.html].

The complete list of 10-cages and the proof of minimality 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 exist 3 distinct {{math|(3,10)}}-cages, the other two being 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. 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.Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018

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)\; \backslash cdot$

:$\backslash cdot(x^2-6)^2\; (x^2-5)^4\; (x^2-2)^2\; (x^4-6\; x^2+3)^8.$