Hamiltonicity in connected regular graphs
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.
hamiltonicity regular graphs combinatorial problems