Toughness, hamiltonicity and split graphs

DOI10.1016/0012-365X(95)00190-8zbMath0855.05079MaRDI QIDQ1916113

Haiko Müller, Dieter Kratsch, Jenő Lehel

Publication date: 26 January 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

split graphpolynomial time algorithmtoughnesshamiltonicity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Related Items

The Hamiltonian properties in \(K_{1,r}\)-free split graphs, Long paths and toughness of \(k\)-trees and chordal planar graphs, 10-tough chordal graphs are Hamiltonian (extended abstract), Hamilton cycles and eigenvalues of graphs, 1-tough cocomparability graphs are hamiltonian, 10-tough chordal graphs are Hamiltonian, Toughness and Hamiltonicity in \(k\)-trees, The complexity of recognizing tough cubic graphs, The complexity of recognizing minimally tough graphs, Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs, On Hamiltonian properties of \(K_{1, r}\)-free split graphs, Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs, Toughness and Hamiltonicity of strictly chordal graphs, Forbidden subgraphs and 2‐factors in 3/2‐tough graphs, Two completely independent spanning trees of split graphs, Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy, Hamiltonicity in Split Graphs - A Dichotomy, Chordality and 2-factors in tough graphs, Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs, Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs, Recognition of split-graphic sequences, On Toughness and Hamiltonicity of 2K₂‐Free Graphs, On the Burkard-Hammer condition for Hamiltonian split graphs, Some properties of \(k\)-trees, Toughness in graphs -- a survey, The completion of a classification for maximal nonhamiltonian Burkard-Hammer graphs, Bipartite toughness and \(k\)-factors in bipartite graphs, Toughness, forbidden subgraphs and pancyclicity, Connected even factors in \(k\)-tree, Toughness, forbidden subgraphs, and Hamilton-connected graphs, Unnamed Item, A necessary condition for maximal nonhamiltonian Burkard-Hammer graphs, The toughness of split graphs, Chvátal’s t 0-Tough Conjecture, Hamiltonian powers in threshold and arborescent comparability graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Recognizing tough graphs is NP-hard
• Finding Hamiltonian circuits in interval graphs
• Matching theory
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• 1-tough cocomparability graphs are hamiltonian
• Toughness and nonhamiltonicity of polyhedral graphs
• Tough graphs and Hamiltonian circuits.
• Toughness and the existence ofk-factors
• The NP-completeness column: an ongoing guide
• Two sufficient conditions for a 2-factor in a bipartite graph
• Toughness, minimum degree, and the existence of 2‐factors
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Depth-First Search and Linear Graph Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Factors of Graphs