Barnette–Bosák–Lederberg graph

In the mathematical field of graph theory, the Barnette–Bosák–Lederberg graph is a cubic (that is, 3-regular) polyhedral graph with no Hamiltonian cycle, the smallest such graph possible.[1] It was discovered in the mid-1960s by Joshua Lederberg, David Barnette, and Juraj Bosák, after whom it is named. It has 38 vertices and 69 edges.[2][3][4]

Barnette–Bosák–Lederberg graph
Vertices38
Edges57
Radius5
Diameter9
Girth4
Chromatic number3
Chromatic index3
PropertiesCubic
Planar
Polyhedral
Table of graphs and parameters

Other larger non-Hamiltonian cubic polyhedral graphs include the 46-vertex Tutte graph and a 44-vertex graph found by Emanuels Grīnbergs using Grinberg's theorem. The Barnette–Bosák–Lederberg graph has a similar construction to the Tutte graph but is composed of two Tutte fragments, connected through a pentagonal prism, instead of three connected through a tetrahedron. Without the constraint of having exactly three edges at every vertex, much smaller non-Hamiltonian polyhedral graphs are possible, including the Goldner–Harary graph and the Herschel graph.

References
  1. Holton, D. A.; McKay, B. D. (1988), "The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices", Journal of Combinatorial Theory, Series B, 45 (3): 305–319, doi:10.1016/0095-8956(88)90075-5
  2. Lederberg, Joshua (1967), "Hamilton circuits of convex trivalent polyhedra (up to 18 vertices)", The American Mathematical Monthly, 74 (5): 522–527, doi:10.2307/2314879, JSTOR 2314879, MR 0211895
  3. Bosák, J. (1967), "Hamiltonian lines in cubic graphs", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 35–46, MR 0221970
  4. Weisstein, Eric W., "Barnette-Bosák-Lederberg Graph", MathWorld
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.