TOPICS
Search

Barnette-Bosák-Lederberg Graph


Barnette-Bosak-LederbergGraph

The Barnette-Bosák-Lederberg graph is a graph on 38 vertices which is the smallest known example of a planar 3-connected nonhamiltonian graph, i.e., the smallest known counterexample to Tait's Hamiltonian graph conjecture. It was discovered by Lederberg (1965), and apparently also by D. Barnette and J. Bosák around the same time. It is illustrated above in two embeddings due to Read and Wilson (1998) and Grünbaum (2003, p. 361), respectively.

The Barnette-Bosák-Lederberg graph is implemented in the Wolfram Language as GraphData["BarnetteBosakLederbergGraph"].

Barnette-Bosak-LederbergGraphMatrices

The figures above show the adjacency, incidence, and graph distance matrices of the Barnette-Bosák-Lederberg graph.

The following table summarizes some properties of the Barnette-Bosák-Lederberg graph.

propertyvalue
automorphism group order2
chromatic number3
chromatic polynomial?
claw-freeno
clique number2
determined by spectrumno
diameter9
distance-regular graphno
edge chromatic number3
edge connectivity3
edge count57
edge transitiveno
Eulerianno
face count21
graph genus0
girth4
Hamiltonianno
Hamiltonian path count?
hypohamiltonianno
hypotraceableno
integral graphno
independence number16
line graphno
perfect matching graphno
planaryes
polyhedral graphyes
radius5
regularyes
square-freeno
symmetricno
traceableyes
triangle-freeyes
vertex connectivity3
vertex count38
vertex transitiveno
weakly regular parameters(38,(3),(0),(0,1,2))

See also

Cubic Nonhamiltonian Graph, Tait's Hamiltonian Graph Conjecture

Explore with Wolfram|Alpha

References

Grünbaum, B. Fig. 17.1.5 in Convex Polytopes, 2nd ed. New York: Springer-Verlag, p. 361, 2003.Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.Pegg, E. Jr. "The Icosian Game, Revisited." Mathematica J. 11, 310-314, 2009.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 274, 1998.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.

Cite this as:

Weisstein, Eric W. "Barnette-Bosák-Lederberg Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html

Subject classifications