Samiksha Jaiswal (Editor)

Balaban 11 cage

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Named after
  
A. T. Balaban

Edges
  
168

Diameter
  
8

Vertices
  
112

Radius
  
6

Girth
  
11

Balaban 11-cage

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