The complexity of recognizing tough cubic graphs

DOI10.1016/S0166-218X(97)00030-9MaRDI QIDQ1372728zbMATH OpenOpenAlexFDO

Authors D. Bauer, Jan van den Heuvel, Aurora Morgana, E. 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) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• Recognizing tough graphs is NP-hard
• On the complexity of recognizing tough graphs
• The complexity of recognizing minimally tough graphs
• scientific article; zbMATH DE number 734468

Cites work

• scientific article; zbMATH DE number 3906530 (Why is no real title available?)
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 734468 (Why is no real title available?)
• scientific article; zbMATH DE number 867714 (Why is no real title available?)
• A Theorem on Planar Graphs
• A theorem on paths in planar graphs
• An upper bound on the shortness exponent of 1-tough, maximal planar graphs
• Connectivity, genus, and the number of components in vertex-deleted subgraphs
• Graph theory
• Hamiltonian results inK1,3-free graphs
• Long Cycles in Digraphs
• On the complexity of recognizing tough graphs
• On the toughness index of planar graphs
• Recognizing tough graphs is NP-hard
• Some Theorems on Abstract Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The smallest 2-connected cubic bipartite planar nonhamiltonian graph
• Tough graphs and Hamiltonian circuits.
• Toughness and the existence ofk-factors
• Toughness, hamiltonicity and split graphs

Cited in

(16)

• Toughness in graphs -- a survey
• The spectrum and toughness of regular graphs
• scientific article; zbMATH DE number 2230266 (Why is no real title available?)
• The complexity of recognizing minimally tough graphs
• Toughness and binding number
• scientific article; zbMATH DE number 734468 (Why is no real title available?)
• Approximation hardness of graphic TSP on cubic graphs
• Cubic time recognition of cocircuit graphs of uniform oriented matroids
• On the complexity of all \(( g , f )\)-factors problem
• An efficient algorithm to compute the toughness in graphs with bounded treewidth
• scientific article; zbMATH DE number 3936535 (Why is no real title available?)
• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• scientific article; zbMATH DE number 6770058 (Why is no real title available?)
• Recognizing tough graphs is NP-hard
• On the complexity of recognizing tough graphs
• Toughness, minimum degree, and spanning cubic subgraphs

This page was built for publication: The complexity of recognizing tough cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372728)