Toughness in graphs -- a survey

DOI10.1007/s00373-006-0649-0zbMath1088.05045OpenAlexW2001161770MaRDI QIDQ2494126

Douglas Bauer, Edward F. Schmeichel, Hajo J. Broersma

Publication date: 16 June 2006

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-006-0649-0

zbMATH Keywords

Hamiltonian graphComputational complexityHamilton cycleChordal graphPlanar graphFactorCircumferenceTriangle-free graphTraceable graph

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items

Toughness of the corona of two graphs, Long paths and toughness of \(k\)-trees and chordal planar graphs, The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample, Toughness and normalized Laplacian eigenvalues of graphs, Graph connectivity and binomial edge ideals, The scattering number of strictly chordal graphs: linear time determination, 10-tough chordal graphs are Hamiltonian (extended abstract), Separation of Cartesian products of graphs into several connected components by the removal of vertices, Forbidden subgraphs for Hamiltonicity of 1-tough graphs, 10-tough chordal graphs are Hamiltonian, Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph, Toughness, binding number and restricted matching extension in a graph, A Brief Account on the Development and Future Research Directions of Connectivity Properties of Interconnection Networks, Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs, A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs, Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs, Cycle lengths in randomly perturbed graphs, The spectrum and toughness of regular graphs, Toughness and Hamiltonicity of strictly chordal graphs, Forbidden subgraphs and 2‐factors in 3/2‐tough graphs, ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphs, An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs, Relationship among triangulations, quadrangulations and optimal 1-planar graphs, Some conditions for Hamiltonian cycles in 1-tough \((K_2 \cup kK_1)\)-free graphs, The fully weighted toughness of a graph, Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs, An Ore-type condition for hamiltonicity in tough graphs and the extremal examples, A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees, Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey, Graph toughness from Laplacian eigenvalues, Toughness, Hamiltonicity and spectral radius in graphs, Unnamed Item, Vulnerability of nearest neighbor graphs, Spanning trees: A survey, Toughness in pseudo-random graphs, Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs, A kind of conditional connectivity of Cayley graphs generated by wheel graphs, A toughness condition for a spanning tree with bounded total excesses, Vulnerability of subclasses of chordal graphs, BIPARTITE MATCHING EXTENDABILITY AND TOUGHNESS, On Toughness and Hamiltonicity of 2K₂‐Free Graphs, Forbidden Induced Subgraphs for Toughness, A survey of some network reliability analysis and synthesis results, A clique-covering sufficient condition for hamiltonicity of graphs, On connectivity of the facet graphs of simplicial complexes, The toughness of Kneser graphs, Drawing graphs as spanners, Bipartite toughness and \(k\)-factors in bipartite graphs, Toughness, forbidden subgraphs and pancyclicity, Implementation of RTO in a large hydrogen network considering uncertainty, Toughness, forbidden subgraphs, and Hamilton-connected graphs, Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs, On the Power of Planned Infections in Networks, Network Topology Vulnerability/Cost Trade-Off: Model, Application, and Computational Complexity, An Ore-type condition for Hamiltonicity in tough graphs, Chvátal’s t 0-Tough Conjecture, \(\ell\)-connectivity, integrity, tenacity, toughness and eigenvalues of graphs

Cites Work

• Long cycles in graphs with large degree sums
• New sufficient conditions for cycles in graphs
• On hamiltonian line graphs and connectivity
• An upper bound on the shortness exponent of 1-tough, maximal planar graphs
• Toughness and Hamiltonicity in \(k\)-trees
• Longest cycles in 3-connected planar graphs
• Recognizing tough graphs is NP-hard
• A simple proof of a theorem of Jung
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Triangle-free graphs whose independence number equals the degree
• Finding Hamiltonian circuits in interval graphs
• Matching theory
• A generalization of a result of Häggkvist and Nicoghossian
• On submodular function minimization
• Toughness and the existence of k-factors. II
• Ramanujan graphs
• On a connection between the existence of k-trees and the toughness of a graph
• A 1-tough nonhamiltonian maximal planar graph
• A remark on Hamiltonian cycles
• The edge Hamiltonian path problem is NP-complete
• Existence of dominating cycles and paths
• A large class of maximally tough graphs
• Hamiltonian properties of graphs with large neighborhood unions
• Geometric algorithms and combinatorial optimization
• A lower bound for the circumference of a graph
• Connectivity, genus, and the number of components in vertex-deleted subgraphs
• Über Hamiltonsche Kreise und unabhängige Ecken in Graphen
• \((2,k)\)-factor-critical graphs and toughness
• Long cycles, degree sums and neighborhood unions
• On the length of longest dominating cycles in graphs
• A generalization of a result of Bauer and Schmeichel
• On the complexity of recognizing tough graphs
• Toughness of graphs and \([2,b\)-factors]
• Maximum and minimum toughness of graphs of small genus
• Toughness and edge-toughness
• On a closure concept in claw-free graphs
• 1-tough cocomparability graphs are hamiltonian
• The complexity of recognizing tough cubic graphs
• Toughness and the existence of \(k\)-factors. IV
• Toughness and the existence of \(k\)-factors. III
• The toughness of split graphs
• Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
• Properties of edge-tough graphs
• Toughness of graphs and the existence of factors
• Toughness and matching extension in graphs
• Long cycles in 3-connected graphs
• Toughness and Hamiltonicity of a class of planar graphs
• Toughness, degrees and 2-factors
• Tough Ramsey graphs without short cycles
• Long cycles in graphs with prescribed toughness and minimum degree
• Hamiltonian degree conditions for tough graphs
• Toughness and spectrum of a graph
• Circumferences in 1-tough graphs
• Toughness and triangle-free graphs
• Non-hamiltonian \(5 \over 4\)-tough maximal planar graphs
• The toughness of cubic graphs
• Toughness, hamiltonicity and split graphs
• On the shortness exponent of 1-tough, maximal planar graphs
• A note on dominating cycles in 2-connected graphs
• \((3, k)\)-factor-critical graphs and toughness
• Not every 2-tough graph is Hamiltonian
• Chordality and 2-factors in tough graphs
• Toughness and nonhamiltonicity of polyhedral graphs
• Long paths and cycles in tough graphs
• Tutte sets in graphs. II: The complexity of finding maximum Tutte sets
• Pancyclic graphs. I
• On Hamilton's ideals
• Large cycles in graphs
• A note on Hamiltonian circuits
• The square of every two-connected graph is Hamiltonian
• Tough graphs and Hamiltonian circuits.
• Shortness exponents of families of graphs
• On Hamiltonian bipartite graphs
• Connected (g, f)-factors
• On k-factor-critical graphs
• A Theorem on Planar Graphs
• Graph Theory and Probability
• TWO THEOREMS IN GRAPH THEORY
• Note on Hamilton Circuits
• Hamiltonian results inK1,3-free graphs
• On the Toughness of a Graph
• Conditions for the Existence of Hamiltonian Circuits in Graphs Based on Vertex Degrees
• Toughness and the existence ofk-factors
• Two sufficient conditions for a 2-factor in a bipartite graph
• Long Cycles in Digraphs
• Longest Cycles in 3-Connected 3-Regular Graphs
• A Remark on Hamiltonian Cycles
• On Maximal Circuits in Finite Graphs
• Long cycles and neighborhood union in 1-tough graphs with large degree sums
• Graph Classes: A Survey
• Longest cycles in tough graphs
• Various results on the toughness of graphs
• On the toughness index of planar graphs
• Toughness, minimum degree, and the existence of 2‐factors
• On the Structure of Non-Hamiltonian Graphs I
• Measures of vulnerability–the integrity family
• Toughness, minimum degree, and the existence of 2‐factors
• On Path-Tough Graphs
• Degree sums for edges and cycle lengths in graphs
• Toughness, minimum degree, and spanning cubic subgraphs
• Toughness and longest cycles in 2-connected planar graphs
• More than one tough chordal planar graphs are Hamiltonian
• Reflections on graph theory
• A sharp lower bound for the circumference of 1‐tough graphs with large degree sums
• 2-factors in triangle-free graphs
• Toughness, trees, and walks
• A theorem on tait colorings with an application to the generalized Petersen graphs
• The binding number of a graph and its Anderson number
• Some Theorems on Abstract Graphs
• Paths and Circuits in Critical Graphs
• Sur le coloriage des graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item