View source for Balaban 10-cage

{{Short description|Cubic graph with 70 nodes and 105 edges}}
{{infobox graph
 | name = Balaban 10-cage
 | image = [[Image:Balaban 10-cage.svg|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 graph|Cubic]]<br>[[Cage (graph theory)|Cage]]<br>[[Hamiltonian graph|Hamiltonian]]
|book thickness=3|queue number=2}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Balaban 10-cage''' or '''Balaban {{math|(3,10)}}-cage''' is a 3-[[regular graph]] with 70 [[Vertex (graph theory)|vertices]] and 105 edges named after [[Alexandru Balaban|Alexandru T. Balaban]].<ref>{{MathWorld|urlname=Balaban10-Cage|title=Balaban 10-Cage}}</ref> Published in 1972,<ref>[[Alexandru Balaban|Alexandru T. Balaban]], ''A trivalent graph of girth ten'', [[Journal of Combinatorial Theory]] Series B '''12''' (1972), 1–5.</ref> It was the first 10-[[cage (graph theory)|cage]] discovered but it is not unique.<ref>Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. [http://citeseer.ist.psu.edu/448980.html].</ref>

The complete list of 10-cages and the proof of minimality was given by Mary R. O'Keefe and Pak Ken Wong.<ref>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.</ref> There exist 3 distinct {{math|(3,10)}}-cages, the other two being the [[Harries graph]] and the [[Harries–Wong graph]].<ref>Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.</ref> Moreover, the Harries–Wong graph and Harries graph are [[Spectral graph theory|cospectral graphs]].

The Balaban 10-cage has [[chromatic number]] 2, [[chromatic index]] 3, [[Distance (graph theory)#Related_concepts|diameter]]	6, [[Girth (graph theory)|girth]] 10 and is [[Hamiltonian path|hamiltonian]]. It is also a 3-[[k-vertex-connected graph|vertex-connected graph]] and 3-[[k-edge-connected graph|edge-connected]]. The [[book thickness]] is 3 and the [[queue number]] is 2.<ref>Jessica Wolz, ''Engineering'' ''Linear Layouts with SAT''. Master Thesis, Universität Tübingen, 2018</ref>

The [[characteristic polynomial]] of the Balaban 10-cage is
: <math>(x-3) (x-2) (x-1)^8 x^2 (x+1)^8 (x+2) (x+3) \cdot</math> 
:<math>\cdot(x^2-6)^2 (x^2-5)^4 (x^2-2)^2 (x^4-6 x^2+3)^8.</math>

==Gallery==
<gallery>
Image:balaban_10-cage_2COL.svg|The [[chromatic number]] of the Balaban 10-cage is&nbsp;2.
Image:balaban_10-cage_3color_edge.svg|The [[chromatic index]] of the Balaban 10-cage is&nbsp;3.
Image: balaban_10-cage_alternative_drawing.svg|Another drawing of the Balaban 10-cage.
</gallery>

==See also==
[[Molecular graph]]<br/>
[[Balaban 11-cage]]

== References ==
{{reflist}}

{{DEFAULTSORT:Balaban 10-Cage}}
[[Category:Individual graphs]]
[[Category:Regular graphs]]