10-tough chordal graphs are Hamiltonian

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.

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2017-01, Vol.122, p.417-427
Main Authors: Kabela, Adam, Kaiser, Tomáš
Format: Article
Language:English
Subjects:
Chordal graph
Hamilton cycle
Hamilton-connected graph
Toughness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2016.07.002