From Surf Wiki (app.surf) — the open knowledge base

Balaban 10-cage

Cubic graph with 70 nodes and 105 edges

Field	Value
name	Balaban 10-cage
image	[[Image:Balaban 10-cage.svg	220px]]
image_caption	The Balaban 10-cage
namesake	Alexandru T. Balaban
vertices	70
edges	105
automorphisms	80
girth	10
diameter	6
radius	6
chromatic_number	2
chromatic_index	3
book_thickness	3
queue_number	2
genus	9
properties	Cubic
Cage
Hamiltonian
book thickness	3	queue number=2

Cage Hamiltonian

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 proof of minimality of the number of vertices was given by Mary R. O'Keefe and Pak Ken Wong. There are 2 other distinct (3,10)-cages, the Harries graph and the Harries–Wong graph. The Harries–Wong graph and Harries graph are also cospectral.

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) \cdot :\cdot(x^2-6)^2 (x^2-5)^4 (x^2-2)^2 (x^4-6 x^2+3)^8.

Gallery

Image:balaban_10-cage_2COL.svg|The chromatic number of the Balaban 10-cage is 2. Image:balaban_10-cage_3color_edge.svg|The chromatic index of the Balaban 10-cage is 3. Image: balaban_10-cage_alternative_drawing.svg|Another drawing of the Balaban 10-cage.

References

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

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

individual-graphs regular-graphs

Want to explore this topic further?

Ask Mako anything about Balaban 10-cage — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report