10-tough chordal graphs are Hamiltonian

DOI10.1016/J.JCTB.2016.07.002MaRDI QIDQ345090zbMATH OpenOpenAlexFDO

Authors Adam Kabela, Tomáš Kaiser

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.02568

zbMATH Keywords

Hamilton cycletoughnesschordal graphHamilton-connected graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Abstract: Chen et al. proved that every 18-tough chordal graph has a Hamilton cycle [Networks 31 (1998), 29-38]. 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.

Recommendations

• 10-tough chordal graphs are Hamiltonian (extended abstract)
• More than one tough chordal planar graphs are Hamiltonian
• Forbidden subgraphs for Hamiltonicity of 1-tough graphs
• Toughness and Hamiltonicity of a class of planar graphs
• Not every 2-tough graph is Hamiltonian

Cites work

• scientific article; zbMATH DE number 1124477 (Why is no real title available?)
• Finding Hamiltonian circuits in interval graphs
• Hall's theorem for hypergraphs
• More than one tough chordal planar graphs are Hamiltonian
• Not every 2-tough graph is Hamiltonian
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tough graphs and Hamiltonian circuits.
• Toughness in graphs -- a survey
• Toughness, hamiltonicity and split graphs

Cited in

(17)

• The structure of minimally t-tough, 2K₂-free graphs
• Long paths and toughness of \(k\)-trees and chordal planar graphs
• A Fan-type condition for cycles in 1-tough and k-connected (P₂ kP₁)-free graphs
• Toughness and Hamiltonicity of a class of planar graphs
• Forbidden subgraphs and 2‐factors in 3/2‐tough graphs
• On minimally 1-tough (P₂ 3P₁)-free graphs
• Hamiltonicity of 1-tough (P₂ KP₁)-free graphs
• 10-tough chordal graphs are Hamiltonian (extended abstract)
• The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs
• The injective chromatic index of a claw-free subcubic graph is at most 6
• Constructions of minimally t-tough regular graphs
• A closure lemma for tough graphs and Hamiltonian degree conditions
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• 4-connected 1-planar chordal graphs are Hamiltonian-connected
• On the minimum degree of minimally 1-tough, triangle-free graphs and minimally 3/2-tough, claw-free graphs
• On the minimum degree of minimally t-tough, claw-free graphs
• 10-Gabriel graphs are Hamiltonian

This page was built for publication: 10-tough chordal graphs are Hamiltonian

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345090)