Hamiltonicity in connected regular graphs |
| |
| Authors: | Daniel W Cranston Suil O |
| |
| Affiliation: | 1. Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, VA 23284, United States;2. Department of Mathematics, The College of William and Mary, Williamsburg, VA 23185, United States |
| |
| Abstract: | 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. |
| |
| Keywords: | Combinatorial problems Hamiltonicity Regular graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
