Daniel W. Cranston, Suil O
Published 2012-04-29Version 1
In 1980, Jackson proved that every 2-connected $k$-regular graph with at most $3k$ vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected $k$-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected $k$-regular graphs without a Hamiltonian cycle.
On Hamiltonicity of {claw, net}-free graphs
Hamiltonian paths and cycles in some 4-uniform hypergraphs
Locating any two vertices on Hamiltonian cycles
![QR code for arXiv:1204.6457 [math.CO]](http://oss.arxitics.com/images/favicon.svg)