10-tough chordal graphs are Hamiltonian

DOI10.1016/J.JCTB.2016.07.002zbMATH Open1350.05087arXiv1508.02568OpenAlexW2962746925MaRDI QIDQ345090FDOQ345090

Authors: Adam Kabela, Tomáš Kaiser 

Publication date: 25 November 2016

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

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.

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

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

zbMATH Keywords

Hamilton cycletoughnesschordal graphHamilton-connected graph

Mathematics Subject Classification ID

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

Cites Work

• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Title not available (Why is that?)
• Finding Hamiltonian circuits in interval graphs
• Toughness, hamiltonicity and split graphs
• Not every 2-tough graph is Hamiltonian
• Toughness in graphs -- a survey
• Tough graphs and Hamiltonian circuits.
• Hall's theorem for hypergraphs
• More than one tough chordal planar graphs are Hamiltonian

Cited In (12)

• The structure of minimally \(t\)-tough, \(2K_2\)-free graphs
• Long paths and toughness of \(k\)-trees and chordal planar graphs
• Toughness and Hamiltonicity of a class of planar graphs
• Forbidden subgraphs and 2‐factors in 3/2‐tough graphs
• Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs
• The injective chromatic index of a claw-free subcubic graph is at most 6
• 10-tough chordal graphs are Hamiltonian (extended abstract)
• The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs
• A closure lemma for tough graphs and Hamiltonian degree conditions
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• On the minimum degree of minimally 1-tough, triangle-free graphs and minimally 3/2-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)