The complexity of recognizing tough cubic graphs

DOI10.1016/S0166-218X(97)00030-9zbMath0888.68092OpenAlexW2148460738MaRDI QIDQ1372728

Jan van den Heuvel, Douglas Bauer, Aurora Morgana, Edward F. Schmeichel

Publication date: 7 January 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

NP-completenesscubic graphstough graphs

Mathematics Subject Classification ID

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

Related Items

The spectrum and toughness of regular graphs, On the complexity of all \(( g , f )\)-factors problem, Toughness and binding number, Toughness in graphs -- a survey, The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An upper bound on the shortness exponent of 1-tough, maximal planar graphs
• Recognizing tough graphs is NP-hard
• The smallest 2-connected cubic bipartite planar nonhamiltonian graph
• Connectivity, genus, and the number of components in vertex-deleted subgraphs
• On the complexity of recognizing tough graphs
• Toughness, hamiltonicity and split graphs
• Tough graphs and Hamiltonian circuits.
• A Theorem on Planar Graphs
• Hamiltonian results inK1,3-free graphs
• Toughness and the existence ofk-factors
• Long Cycles in Digraphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• On the toughness index of planar graphs
• Some Theorems on Abstract Graphs
• A theorem on paths in planar graphs