Balaban 11-cage

Template:Short description Template:Infobox graph 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. 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.

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)x^{12}(x^2-6{)}^5(x^2-2{)}^{12}(x^3-x^2-4x+2{)}^2\cdot$

$\cdot (x^3+x^2-6x-2)(x^4-x^3-6x^2+4x+4{)}^4\cdot$

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

The automorphism group of the Balaban 11-cage is of order 64.

Gallery

• 
  The chromatic number of the Balaban 11-cage is 3.
• 
  The chromatic index of the Balaban 11-cage is 3.
• 
  Alternative drawing of the Balaban 11-cage.

References

• Template:Citation