Graphs with no 2δ+ 1 cycle

2003/07/09 by Galen E. Turner III, Turner, Galen E.
Mathematics · #05C35 #05C38 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05C38 #msc:05C75

paper · pdf · doi:10.48550/arxiv.math/0307123

4 pages

arxiv created 2003/07/09 · arxiv updated 2009/12/01

Abstract

Dirac proved that any graph with minimum vertex degree δ contains either a cycle of length at least 2δ or a Hamilton cycle. Motivated by this result, we characterize those graphs having no cycle longer than 2δ.

Related

• Algorithmic Extensions of Dirac's Theorem
• On a property of 2-connected graphs and Dirac's Theorem
• A Simple Extension of Dirac's Theorem on Hamiltonicity
• Long Cycles in 1-tough Graphs
• A Rainbow Dirac's Theorem