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

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