On the circumference, connectivity and dominating cycles

2009/06/10 by Zh. G. Nikoghosyan, Nikoghosyan, Zh. G.
Computer Science · Mathematics · #05C38 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO #msc:05C38 #msc:05C40

paper · pdf · doi:10.48550/arxiv.0906.1857

31 pages

arxiv created 2009/06/10 · openalex publication_date 2009/06/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Every 4-connected graph with minimum degree δ and connectivity κ either has a cycle of length at least 4δ-2κ or has a dominating cycle.

Citations

• Some Theorems on Abstract Graphs

Related

• Large cycles in 4-connected graphs
• On the Circumference of Essentially 4-connected Planar Graphs
• Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3
• The circumference of a graph with given minimum degree and clique number
• Cubic graphs with large circumference deficit