Not every 2-tough graph is Hamiltonian
From MaRDI portal
A long standing conjecture due to V. Chvátal was that any \(2\)-tough graph is Hamiltonian. A very clever example is presented that disproves this conjecture. More specifically, it is shown for any \(\epsilon > 0\), there is a \((9/4 - \epsilon)\)-tough graph that does not contain a Hamiltonian path. In lack manner a \((7/4 - \epsilon)\)-tough chordal graph that has no Hamiltonian path is presented. The latter result gives a lower bound to the toughness that will imply Hamiltonian in chordal graphs as opposed to the upper bound of \(18\) of \textit{G. Chen, M. S. Jacobson, A. Kézdy} and \textit{J. E. Lehel} [Networks 31, No. 1, 29-38 (1998; Zbl 0894.90150)].
Recommendations
Cites work
- Chordality and 2-factors in tough graphs
- Graph theory with applications
- scientific article; zbMATH DE number 3668667 (Why is no real title available?)
- scientific article; zbMATH DE number 1124477 (Why is no real title available?)
- Tough graphs and Hamiltonian circuits.
- Toughness and the existence ofk-factors
- Toughness, minimum degree, and the existence of 2‐factors
- Toughness, minimum degree, and the existence of 2‐factors
Cited in
(81)- Bipartite toughness and \(k\)-factors in bipartite graphs
- Being Hamiltonian is not a Tutte invariant
- 9-connected claw-free graphs are Hamilton-connected
- Long paths and toughness of \(k\)-trees and chordal planar graphs
- Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs
- An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs
- Toughness and Hamiltonicity of a class of planar graphs
- Chordality and 2-factors in tough graphs
- The toughness of Kneser graphs
- Toughness, forbidden subgraphs and pancyclicity
- The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs
- Toughness, forbidden subgraphs, and Hamilton-connected graphs
- An Ore-type condition for Hamiltonicity in tough graphs
- Hamilton cycles in line graphs of 3-hypergraphs
- Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
- Implementation of RTO in a large hydrogen network considering uncertainty
- Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
- Hamiltonian path saturated graphs with small size
- Toughness in graphs -- a survey
- A note on interconnecting matchings in graphs
- Using integer programming to search for counterexamples: a case study
- Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
- A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs
- Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
- Toughness, Hamiltonicity and spectral radius in graphs
- scientific article; zbMATH DE number 5936422 (Why is no real title available?)
- 10-tough chordal graphs are Hamiltonian (extended abstract)
- Forbidden subgraphs for Hamiltonicity of 1-tough graphs
- 10-tough chordal graphs are Hamiltonian
- scientific article; zbMATH DE number 4139802 (Why is no real title available?)
- The spectrum and toughness of regular graphs
- Toughness, minimum degree, and the existence of 2‐factors
- On the 1-fault Hamiltonicity for graphs satisfying Ore's theorem
- More than one tough chordal planar graphs are Hamiltonian
- Best monotone degree conditions for graph properties: a survey
- The signless Laplacian or adjacency spectral radius of bicyclic graphs with given number of cut edges
- On the Power of Planned Infections in Networks
- On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
- Chvátal's \(t_{0}\)-tough conjecture
- scientific article; zbMATH DE number 2230266 (Why is no real title available?)
- Partitioning vertices of 1-tough graphs into paths
- A large set of non-Hamiltonian graphs
- Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs
- Toughness and spanning trees in K4‐minor‐free graphs
- Forbidden subgraphs and 2‐factors in 3/2‐tough graphs
- The structure of minimally t-tough, 2K₂-free graphs
- Some conditions for Hamiltonian cycles in 1-tough (K₂ kK₁)-free graphs
- Hamiltonicity of 1-tough (P₂ KP₁)-free graphs
- An Ore-type condition for hamiltonicity in tough graphs and the extremal examples
- A closure lemma for tough graphs and Hamiltonian degree conditions
- Disproof of a conjecture on minimally \(t\)-tough graphs
- Spanning trees: A survey
- How many conjectures can you stand? A survey
- Constructions of minimally t-tough regular graphs
- An upper bound on path cover number of regular graphs and its application to Hamiltonian cycle in tough graphs
- Hamiltonicity of Cartesian products of graphs
- Toughness, Hamiltonicity and eigenvalues of graphs
- On minimally t-tough graphs with t 1
- Wiener-type invariants of pancyclicity for t-tough graphs
- Toughness properties of arbitrarily partitionable graphs
- A spectral condition for Hamilton cycles in tough bipartite graphs
- Spectral radius and Hamiltonicity in split graphs
- 4-connected 1-planar chordal graphs are Hamiltonian-connected
- Spectral extremal problems on factors in tough graphs, and beyond
- Strengthening some complexity results on toughness of graphs
- A construction of a 3/2-tough plane triangulation with no 2-factor
- Spectral conditions of pancyclicity for t-tough graphs
- Some properties of \(k\)-trees
- On minimally 1-tough (P₂ 3P₁)-free graphs
- The circumference of 2-tough graphs
- Some conditions for pancyclicity in t-tough graphs
- Eigenvalues and factors: a survey
- Every 2k-connected (P₂ kP₁)-free graph with toughness greater than one is Hamiltonian-connected
- On prism-Hamiltonian bipartite graphs and toughness
- Minimum degrees of minimally \(\frac{1}{k}\)-tough graphs
- Hamilton cycles in tough (2P₂ P₁)-free graphs
- Size conditions for pancyclicity of t-tough graphs
- Toughness and prism-Hamiltonicity of \(P_4\)-free graphs
- Toughness and Hamiltonicity in k-trees
- Smallest claw-free, 2-connected, nontraceable graphs and the construction of maximal nontraceable graphs
- Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs
This page was built for publication: Not every 2-tough graph is Hamiltonian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962051)
