The complexity of recognizing tough cubic graphs

DOI10.1016/S0166-218X(97)00030-9zbMATH Open0888.68092OpenAlexW2148460738MaRDI QIDQ1372728FDOQ1372728

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

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

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)

Cites Work

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

Cited In (16)

• Toughness in graphs -- a survey
• Title not available (Why is that?)
• The spectrum and toughness of regular graphs
• The complexity of recognizing minimally tough graphs
• Toughness and binding number
• Title not available (Why is that?)
• Approximation hardness of graphic TSP on cubic graphs
• Cubic time recognition of cocircuit graphs of uniform oriented matroids
• An efficient algorithm to compute the toughness in graphs with bounded treewidth
• On the complexity of all \(( g , f )\)-factors problem
• Title not available (Why is that?)
• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• Title not available (Why is that?)
• 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)