| Balaban 11-cage | |
| Namesake: | Alexandru T. Balaban |
| Vertices: | 112 |
| Edges: | 168 |
| Automorphisms: | 64 |
| Girth: | 11 |
| Radius: | 6 |
| Diameter: | 8 |
| Chromatic Number: | 3 |
| Chromatic Index: | 3 |
| Independence Number: | 52 |
| Properties: | Cubic Cage Hamiltonian |
In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3,11)-cage is a 3-regular graph with 112 vertices and 168 edges named after Alexandru T. Balaban.
The Balaban 11-cage is the unique (3,11)-cage. It was discovered by Balaban in 1973.[1] The uniqueness was proved by Brendan McKay and Wendy Myrvold in 2003.
The Balaban 11-cage is a Hamiltonian graph and can be constructed by excision from the Tutte 12-cage by removing a small subtree and suppressing the resulting vertices of degree two.[2]
It has independence number 52, chromatic number 3, chromatic index 3, radius 6, diameter 8 and girth 11. It is also a 3-vertex-connected graph and a 3-edge-connected graph.
The characteristic polynomial of the Balaban 11-cage is:
(x-3)x12(x2-6)5(x2-2)12(x3-x2-4x+2)2 ⋅
⋅ (x3+x2-6x-2)(x4-x3-6x2+4x+4)4 ⋅
⋅ (x5+x4-8x3-6x2+12x+4)8
The automorphism group of the Balaban 11-cage is of order 64.[2]