Balaban 10-cage

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.[1] Published in 1972,[2] It was the first (3,10)-cage discovered but it is not unique.[3]

Balaban 10-cage
The Balaban 10-cage
Named afterAlexandru T. Balaban
Vertices70
Edges105
Radius6
Diameter6
Girth10
Automorphisms80
Chromatic number2
Chromatic index3
Book thickness3
Queue number2
PropertiesCubic
Cage
Hamiltonian
Table of graphs and parameters

The complete list of (3-10)-cages and the proof of minimality was given by Mary R. O'Keefe and Pak Ken Wong.[4] There exist 3 distinct (3-10)-cages, the other two being the Harries graph and the Harries–Wong graph.[5] 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 a 3-edge-connected graph. The book thickness is 3 and the queue number is 2.[6]

The characteristic polynomial of the Balaban 10-cage is

  • The chromatic number of the Balaban 10-cage is 2.
  • The chromatic index of the Balaban 10-cage is 3.
  • Alternative drawing of the Balaban 10-cage.
gollark: TOML does still allow weird stuff like, say, IP addresses, to be handled as strings.
gollark: Look at JSON.
gollark: If you don't have a consistent format for dates and whatnot, bad things happen.
gollark: If everything was UTF-8 strings and then application-parsed they would all be handled slightly differently by each library and it would be bad.
gollark: Also, probably more interoperability.

See also

Molecular graph

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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.