Toughness in graphs -- a survey

DOI10.1007/S00373-006-0649-0zbMATH Open1088.05045OpenAlexW2001161770MaRDI QIDQ2494126FDOQ2494126

Authors: D. Bauer, Hajo Broersma, E. Schmeichel 

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

Recommendations

• scientific article; zbMATH DE number 434902
• Tough graphs and Hamiltonian circuits.
• Toughness and edge-toughness
• On the Toughness of Cycle Permutation Graphs
• Chvátal's \(t_{0}\)-tough conjecture

zbMATH Keywords

Hamilton cycleHamiltonian graphComputational complexityChordal graphFactorPlanar graphCircumferenceTriangle-free graphTraceable graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (65)

• The spectrum and toughness of regular graphs
• Toughness of infinite graphs.
• A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees
• Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph
• Graph toughness from Laplacian eigenvalues
• A kind of conditional connectivity of Cayley graphs generated by wheel graphs
• Long paths and toughness of \(k\)-trees and chordal planar graphs
• Spanning trees: A survey
• An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs
• On the Power of Planned Infections in Networks
• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs
• Forbidden subgraphs and 2‐factors in 3/2‐tough graphs
• Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs.
• A survey of some network reliability analysis and synthesis results
• Results on toughness in graphs under heavy subgraph conditions
• A brief account on the development and future research directions of connectivity properties of interconnection networks
• Bipartite toughness and \(k\)-factors in bipartite graphs
• The scattering number of strictly chordal graphs: linear time determination
• Title not available (Why is that?)
• Cycle lengths in randomly perturbed graphs
• Toughness and Hamiltonicity of strictly chordal graphs
• The toughness of Kneser graphs
• Drawing graphs as spanners
• Separation of Cartesian products of graphs into several connected components by the removal of vertices
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• 10-tough chordal graphs are Hamiltonian (extended abstract)
• Toughness, forbidden subgraphs and pancyclicity
• Toughness, forbidden subgraphs, and Hamilton-connected graphs
• Title not available (Why is that?)
• Relationship among triangulations, quadrangulations and optimal 1-planar graphs
• Toughness in pseudo-random graphs
• Forbidden subgraphs for Hamiltonicity of 1-tough graphs
• On connectivity of the facet graphs of simplicial complexes
• Toughness, binding number and restricted matching extension in a graph
• 10-tough chordal graphs are Hamiltonian
• A note on Hamiltonian cycles in 4-tough \((P_2 \cup KP_1)\)-free graphs
• Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs
• A clique-covering sufficient condition for hamiltonicity of graphs
• Network topology vulnerability/cost trade-off: model, application, and computational complexity
• ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphs
• A toughness condition for a spanning tree with bounded total excesses
• Toughness of the corona of two graphs
• An Ore-type condition for Hamiltonicity in tough graphs
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• Toughness, Hamiltonicity and spectral radius in graphs
• Implementation of RTO in a large hydrogen network considering uncertainty
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Graph connectivity and binomial edge ideals
• Chvátal's \(t_{0}\)-tough conjecture
• Forbidden Induced Subgraphs for Toughness
• BIPARTITE MATCHING EXTENDABILITY AND TOUGHNESS
• \(\ell\)-connectivity, integrity, tenacity, toughness and eigenvalues of graphs
• Toughness and normalized Laplacian eigenvalues of graphs
• Vulnerability of subclasses of chordal graphs
• Vulnerability of nearest neighbor graphs
• Vertex cut, eigenvalues, \([a,b]\)-factors and toughness of connected bipartite graphs
• Toughness and spectral radius in 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 unified combinatorial view beyond some spectral properties
• \(l\)-connectivity, \(l\)-edge-connectivity and spectral radius of graphs
• On prism-Hamiltonian bipartite graphs

This page was built for publication: Toughness in graphs -- a survey

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