Name
Abstract | ||
|---|---|---|
We consider toughness conditions that guarantee the existence of a hamiltonian cycle in k-trees, a subclass of the class of chordal graphs. By a result of Chen et al. 18-tough chordal graphs are hamiltonian, and by a result of Bauer et al. there exist nontraceable chordal graphs with toughness arbitrarily close to 74. It is believed that the best possible value of the toughness guaranteeing hamiltonicity of chordal graphs is less than 18, but the proof of Chen et al. indicates that proving a better result could be very complicated. We show that every 1-tough 2-tree on at least three vertices is hamiltonian, a best possible result since 1-toughness is a necessary condition for hamiltonicity. We generalize the result to k-trees for k>=2: Let G be a k-tree. If G has toughness at least (k+1)/3, then G is hamiltonian. Moreover, we present infinite classes of nonhamiltonian 1-tough k-trees for each k>=3. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.disc.2005.11.051 | Discrete Mathematics |
Keywords | Field | DocType |
complexity 1991 msc:05c45,toughness,hamiltonian graph,t-tough graph,chordal graph,k-tree,t -tough graph,traceable graph,05c45,k -tree,05c35,complexity,t,k,hamiltonian cycle | Discrete mathematics,Graph,Combinatorics,Indifference graph,Vertex (geometry),Hamiltonian (quantum mechanics),Hamiltonian path,K-tree,Chordal graph,Toughness,Mathematics | Journal |
Volume | Issue | ISSN |
307 | 7-8 | Discrete Mathematics |
Citations | PageRank | References |
4 | 0.53 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hajo Broersma | 1 | 741 | 87.39 |
| Liming Xiong | 2 | 109 | 16.30 |
| Kiyoshi Yoshimoto | 3 | 133 | 22.65 |