Long cycles in graphs with large degree sums

DOI10.1016/0012-365X(90)90055-MzbMath0713.05041OpenAlexW2019698871MaRDI QIDQ749553

Douglas Bauer, Aurora Morgana, Edward F. Schmeichel, Henk Jan Veldman

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0012-365x(90)90055-m

zbMATH Keywords

independence numberdominating cyclet-tough

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Related Items (36)

Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion ⋮ Long cycles in graphs containing a 2-factor with many odd components ⋮ Hamiltonian cycles in n‐extendable graphs ⋮ A generalization of a result of Häggkvist and Nicoghossian ⋮ Long cycles in graphs with prescribed toughness and minimum degree ⋮ A common generalization of Chvátal-Erdös' and Fraisse's sufficient conditions for hamiltonian graphs ⋮ Binding Number, Minimum Degree, and Cycle Structure in Graphs ⋮ Cycles through prescribed vertices with large degree sum ⋮ Circumferences in 1-tough graphs ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ Cycles through subsets with large degree sums ⋮ A note on dominating cycles in 2-connected graphs ⋮ Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey ⋮ \(k\)-factors and Hamilton cycles in graphs ⋮ Some results on the A _α -eigenvalues of a graph ⋮ An Ore-type condition for hamiltonicity in tough graphs and the extremal examples ⋮ Toughness, Hamiltonicity and spectral radius in graphs ⋮ Recognizing tough graphs is NP-hard ⋮ A simple proof of a theorem of Jung ⋮ Hamiltonian properties of graphs with large neighborhood unions ⋮ On Hamiltonian cycles in balanced \(k\)-partite graphs ⋮ Relative length of longest paths and cycles in 3-connected graphs ⋮ Graph invariants and large cycles: a survey ⋮ Toughness in graphs -- a survey ⋮ Hamiltonicity in Partly claw-free graphs ⋮ Degree sums, \(k\)-factors and Hamilton cycles in graphs ⋮ Long cycles in graphs with large degree sums ⋮ Unnamed Item ⋮ An Ore-type condition for Hamiltonicity in tough graphs ⋮ Hamiltonian cycles in 1-tough graphs ⋮ Long cycles, degree sums and neighborhood unions ⋮ All nonhamiltonian tough graphs satisfying a 3-degree sum and Fan-type conditions ⋮ 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 ⋮ A generalization of Ore's Theorem involving neighborhood unions

Cites Work

• Long cycles in graphs with large degree sums
• A simple proof of a theorem of Jung
• Existence of dominating cycles and paths
• Über Hamiltonsche Kreise und unabhängige Ecken in Graphen
• Tough graphs and Hamiltonian circuits.
• Conditions for the Existence of Hamiltonian Circuits in Graphs Based on Vertex Degrees
• On Maximal Circuits in Finite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Long cycles in graphs with large degree sums