On the necessity of Chvátal’s Hamiltonian degree condition
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 Chvátal’s sufficient condition is also necessary. In contrast, we essentia...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-10-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1080/09728600.2020.1834337 |
| Summary: | 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 Chvátal’s sufficient condition is also necessary. In contrast, we essentially prove that for every , the sufficient condition of Bondy and Boesch for forcible k-connectedness is not necessary in the same way. |
|---|---|
| ISSN: | 0972-8600 2543-3474 |