Title of article
A large set of non-Hamiltonian graphs Original Research Article
Author/Authors
Gyula Y. Katona، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2001
Pages
17
From page
99
To page
115
Abstract
It is proved that the set of not-1-edge-tough graphs (N1ET) is a better approximation for the set of non-Hamiltonian graphs then the previously given sets. The best previous approximation is the set of non-sub-2-factor graphs (NS2F). The main result of the present article is that the set N1ET−NS2F is DP-complete, which suggests that N1ET is essentially larger than NS2F.
Keywords
Toughness , Edge-toughness , Hamiltonian cycle
Journal title
Discrete Applied Mathematics
Serial Year
2001
Journal title
Discrete Applied Mathematics
Record number
885319
Link To Document