New sufficient condition for Hamiltonian paths
Landon Jennings · Rice Research Repository (Rice University) · 2008
This paper proves a sufficient condition for the existence of Hamiltonian paths in simple connected graphs. This condition was conjectured in 2006 by a computer program named Graffiti.pc. Given examples will show that this new condition detects Hamiltonian paths that a theorem by Chvatal does not. A second condition conjectured by Graffiti.pc is shown to satisfy Chvatal's condition. Thus this second conjecture, while true, does not improve on known results.