Misplaced Pages

Balaban 10-cage

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Cubic graph with 70 nodes and 105 edges
Balaban 10-cage
The Balaban 10-cage
Named afterAlexandru T. Balaban
Vertices70
Edges105
Radius6
Diameter6
Girth10
Automorphisms80
Chromatic number2
Chromatic index3
Genus9
Book thickness3
Queue number2
PropertiesCubic
Cage
Hamiltonian
Table of graphs and parameters

In the mathematical field of graph theory, the Balaban 10-cage or Balaban (3,10)-cage is a 3-regular graph with 70 vertices and 105 edges named after Alexandru T. Balaban. Published in 1972, It was the first 10-cage discovered but it is not unique.

The complete list of 10-cages and the proof of minimality was given by Mary R. O'Keefe and Pak Ken Wong. There exist 3 distinct (3,10)-cages, the other two being the Harries graph and the Harries–Wong graph. Moreover, the Harries–Wong graph and Harries graph are cospectral graphs.

The Balaban 10-cage has chromatic number 2, chromatic index 3, diameter 6, girth 10 and is hamiltonian. It is also a 3-vertex-connected graph and 3-edge-connected. The book thickness is 3 and the queue number is 2.

The characteristic polynomial of the Balaban 10-cage is

( x − 3 ) ( x − 2 ) ( x − 1 ) 8 x 2 ( x + 1 ) 8 ( x + 2 ) ( x + 3 ) ⋅ {\displaystyle (x-3)(x-2)(x-1)^{8}x^{2}(x+1)^{8}(x+2)(x+3)\cdot }
⋅ ( x 2 − 6 ) 2 ( x 2 − 5 ) 4 ( x 2 − 2 ) 2 ( x 4 − 6 x 2 + 3 ) 8 . {\displaystyle \cdot (x^{2}-6)^{2}(x^{2}-5)^{4}(x^{2}-2)^{2}(x^{4}-6x^{2}+3)^{8}.}

Gallery

See also

Molecular graph
Balaban 11-cage

References

  1. Weisstein, Eric W. "Balaban 10-Cage". MathWorld.
  2. Alexandru T. Balaban, A trivalent graph of girth ten, Journal of Combinatorial Theory Series B 12 (1972), 1–5.
  3. Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. .
  4. 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.
  5. Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.
  6. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018
Categories: