A generalization of a theorem of Nash-Williams


Abstract in English

In 1972, Chvatal 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. Nash-Williams gave examples of forcibly hamiltonian n-sequences that do not satisfy Chvatlas condition for every n at least 5. In this note we generalize the Nash-Williams examples, and use this generalization to generate Omega(2^n/n^.5) forcibly hamiltonian n-sequences that do not satisfy Chvatals condition

Download