A Sharp Bound for the Circumference in t-tough graphs with t>1

2012/04/29 by Zh. G. Nikoghosyan, Nikoghosyan, Zh. G.
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1204.6515

29 pages

arxiv created 2012/04/29 · openalex publication_date 2012/04/29 · arxiv updated 2012/05/01 · openalex created_date 2022/08/29 · openalex updated_date 2026/07/28

Abstract

It is proved that if G is a t-tough graph of order n and minimum degree δ with t>1 then either G has a cycle of length at least min\n,2δ+5\ or G is the Petersen graph.

Related

• Hamilton and long cycles in t-tough graphs with t>1
• Proof of a conjecture of Bauer, Fan and Veldman
• The circumference of a graph with given minimum degree and clique number
• A Degree Condition for Dominating Cycles in t-tough Graphs with t>1
• Cubic graphs with large circumference deficit