The toughness of split graphs

DOI10.1016/S0012-365X(98)00156-3zbMath0955.05103OpenAlexW2047734515MaRDI QIDQ1584388

Gerhard J. Woeginger

Publication date: 2 November 2000

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(98)00156-3

zbMATH Keywords

graph algorithmHamiltonian cycletoughness of split graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (15)

Edge vulnerability parameters of split graphs ⋮ The complexity of recognizing minimally tough graphs ⋮ ISOLATED SCATTERING NUMBER OF SPLIT GRAPHS AND GRAPH PRODUCTS ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ A complete characterization of bidegreed split graphs with four distinct signless Laplacian eigenvalues ⋮ On Toughness and Hamiltonicity of 2K₂‐Free Graphs ⋮ Toughness in graphs -- a survey ⋮ Vulnerability parameters of split graphs ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ Edge vulnerability parameters of bisplit graphs ⋮ Bipartite toughness and \(k\)-factors in bipartite graphs ⋮ Unnamed Item ⋮ Vulnerability of super connected split graphs and bisplit graphs ⋮ Unnamed Item ⋮ Maximally and super connected multisplit graphs and digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Recognizing tough graphs is NP-hard
• On submodular function minimization
• Geometric algorithms and combinatorial optimization
• Toughness, hamiltonicity and split graphs
• Tough graphs and Hamiltonian circuits.

This page was built for publication: The toughness of split graphs