Better approximations of non-Hamiltonian graphs

AbstractAlthough there have been a lot of efforts to seek nice characterization of non-Hamiltonian graphs, little progress has been made so far. An important progress was achieved by Chvátal [5, 6]who introduced the class of non-1-tough graphs (N1T) and the class of non-sub-2-factor graphs (NS2F). Both contain only non-Hamiltonian graphs and the conditions for membership can be checked in non-deterministic polynomial time. Also it is known thatN1T ⊂- NS2F. Chvátal posed an open question about the complexity of those classes, i.e., whether or not they are NP-complete [6].Recently, Bauer et al. {2}proved thatN1T is NP-complete. In this paper we prove: (i)NS2F is also NP-complete. (ii)NS2F - N1T is Dp-complete, namely, the former characterization for non-Hamiltonian graphs is essentially better than the latter, (iii) Those results are still true for the bounded-degree graphs