Balaban 11 cage - Alchetron, The Free Social Encyclopedia

Named after A. T. Balaban Edges 168 Diameter 8		Vertices 112 Radius 6 Girth 11

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 A. T. Balaban.

The Balaban 11-cage is the unique (3-11)-cage. It was discovered by Balaban in 1973. The uniqueness was proved by McKay and 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.

Algebraic properties

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 − 4 x + 2 ) 2 ⋅ ⋅ ( x 3 + x 2 − 6 x − 2 ) ( x 4 − x 3 − 6 x 2 + 4 x + 4 ) 4 ( x 5 + x 4 − 8 x 3 − 6 x 2 + 12 x + 4 ) 8 .

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

References

Balaban 11-cage Wikipedia

(Text) CC BY-SA