10-tough chordal graphs are Hamiltonian

详细信息    查看全文

• 作者：Adam Kabela^a ; ^{kabela@kma.zcu.cz} ; Tomá ; &scaron ; Kaiser^b ; ^{kaisert@kma.zcu.cz}
• 关键词：Toughness ; Hamilton cycle ; Chordal graph ; Hamilton-connected graph
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：417-427
• 全文大小：335 K
• 卷排序：122

文摘

Chen et al. (1998) proved that every 18-tough chordal graph has a Hamilton cycle. Improving upon their bound, we show that every 10-tough chordal graph is Hamiltonian (in fact, Hamilton-connected). We use Aharoni and Haxell's hypergraph extension of Hall's Theorem as our main tool.