Not every 2-tough graph is Hamiltonian
From MaRDI portal
Publication:1962051
DOI10.1016/S0166-218X(99)00141-9zbMath0934.05083OpenAlexW2007167081WikidataQ29037944 ScholiaQ29037944MaRDI QIDQ1962051
Douglas Bauer, Hajo J. Broersma, Henk Jan Veldman
Publication date: 9 April 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00141-9
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)
Related Items
Long paths and toughness of \(k\)-trees and chordal planar graphs ⋮ Toughness and Hamiltonicity of a class of planar graphs ⋮ Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday) ⋮ Hamilton cycles in line graphs of 3-hypergraphs ⋮ 10-tough chordal graphs are Hamiltonian (extended abstract) ⋮ Forbidden subgraphs for Hamiltonicity of 1-tough graphs ⋮ 10-tough chordal graphs are Hamiltonian ⋮ Toughness and Hamiltonicity in \(k\)-trees ⋮ Smallest claw-free, 2-connected, nontraceable graphs and the construction of maximal nontraceable graphs ⋮ Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs ⋮ 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 ⋮ Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs ⋮ Toughness and spanning trees in K4‐minor‐free graphs ⋮ The spectrum and toughness of regular graphs ⋮ Forbidden subgraphs and 2‐factors in 3/2‐tough graphs ⋮ An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs ⋮ The structure of minimally \(t\)-tough, \(2K_2\)-free graphs ⋮ Some conditions for Hamiltonian cycles in 1-tough \((K_2 \cup kK_1)\)-free graphs ⋮ Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-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 ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Toughness, Hamiltonicity and spectral radius in graphs ⋮ On the 1-fault Hamiltonicity for graphs satisfying Ore's theorem ⋮ Chordality and 2-factors in tough graphs ⋮ Spanning trees: A survey ⋮ How many conjectures can you stand? A survey ⋮ Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs ⋮ 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 ⋮ Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs ⋮ On Toughness and Hamiltonicity of 2K2‐Free Graphs ⋮ Partitioning vertices of 1-tough graphs into paths ⋮ Hamiltonian path saturated graphs with small size ⋮ Some properties of \(k\)-trees ⋮ Toughness in graphs -- a survey ⋮ A large set of non-Hamiltonian graphs ⋮ A note on interconnecting matchings in graphs ⋮ The toughness of Kneser graphs ⋮ Bipartite toughness and \(k\)-factors in bipartite graphs ⋮ Toughness, forbidden subgraphs and pancyclicity ⋮ The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs ⋮ Implementation of RTO in a large hydrogen network considering uncertainty ⋮ Toughness, forbidden subgraphs, and Hamilton-connected graphs ⋮ On the Power of Planned Infections in Networks ⋮ Unnamed Item ⋮ An Ore-type condition for Hamiltonicity in tough graphs ⋮ Toughness and prism-Hamiltonicity of \(P_4\)-free graphs ⋮ Chvátal’s t 0-Tough Conjecture ⋮ 9-connected claw-free graphs are Hamilton-connected
Cites Work
