On the necessity of Chvátal’s Hamiltonian degree condition
Douglas C. Bauer, Linda M. Lesniak, A. Nevo, Edward F. Schmeichel · AKCE International Journal of Graphs and Combinatorics · 2020
In 1972 Chvátal gave a well-known sufficient condition for a graphical sequence to be forcibly Hamiltonian, and showed that in some sense his condition is best possible. In this paper, we conjecture that with probability 1 as n → ∞ , Chvátal’s sufficient condition is also necessary. In contrast, we essentially prove that for every k ≥ 1 , the sufficient condition of Bondy and Boesch for forcible k-connectedness is not necessary in the same way.