The term "Grinberg graphs" is used in this work for a number of small cubicpolyhedral graphs
constructed by Grinberg (1968) as counterexamples
to Tait's Hamiltonian graph conjecture
(i.e., that every cubic polyhedral graph is Hamiltonian). These nonhamiltonian
graphs are all associated with Grinberg's name, with the 44-vertex example being
referred to as "Grinberg's graph" (Read and Wilson 1998, p. 274) and
the 46-vertex example as "the Grinberg graph" (Bondy and Murty 1976, p. 162;
Thomassen 1981). The 44-vertex graph is the smallest cubic
polyhedral nonhamiltonian graph
that is cyclically 5-connected (Grünbaum 1974).
The 42-vertex graph can be derived from the 44-vertex graph by deleting a suitable graph
edge, removing its two endpoints, and joining the other two neighbors of each
endpoint (Faulkner and Younger 1974). According to Zamfirescu (1976), the 44-vertex
graph was discovered independently by Grinberg (1968) and
Tutte (Grünbaum 1970, Faulkner and Younger 1974).
Additional graph drawings are illustrated above for the Grinberg graphs.
Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Bondy, J. A.
and Murty, U. S. R. Fig. 9.27 in Graph
Theory with Applications. New York: North Holland, p. 162, 1976.Bondy,
J. A. and Murty, U. S. R. Graph
Theory. Berlin, Germany: Springer-Verlag, p. 480, 2008.Faulkner,
G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps."
Disc. Math.7, 67-74, 1974.Grinberg, E. J. "Plane
Homogeneous Graphs of Degree Three without Hamiltonian Circuits." Latvian
Math. Yearbook, Izdat. Zinatne, Riga4, 51-58, 1968.Grünbaum,
B. "Polytopes, Graphs, and Complexes." Bull. Amer. Math. Soc.76,
1131-1201, 1970.Grünbaum, B. "Vertices Missed by Longest Paths
or Circuits." J. Combin. Th. A17, 31-38, 1974.House
of Graphs. Grinberg Graphs. Grinberg
Graph 42, Grinberg Graph 44,
and Grinberg Graph 46.Read,
R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, p. 274, 1998.Sachs,
H. "Ein von Kozyrev und Grinberg angegebener nicht-Hamiltonischer kubischer
planarer Graph." In Beiträge zur Graphentheorie. Leipzig, Germany:
Teubner, pp. 127-130, 1968.Thomassen, C. "Planar Cubic Hypohamiltonian
and Hypotraceable Graphs." J. Comb. Th. B30, 36-44, 1981.Zamfirescu,
T. "On Longest Paths and Circuits in Graphs." Math. Scand.38,
211-239, 1976.
