Proof of a conjecture of Bauer, Fan and Veldman

2013/09/20 by Tri Lai, Lai, Tri
Computer Science · Mathematics · #05C35 #05C38 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C35 #msc:05C38

paper · pdf · doi:10.48550/arxiv.1309.5379

25 pages,5 figures

openalex publication_date 2013/09/20 · arxiv created 2013/09/26 · arxiv updated 2013/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a 1-tough graph G we define σ₃(G) = min\°(u) + °(v)+ °(w): \u, v, w\ is an independent set of vertices\ and NC2(G)=min \|N(u)∪ N(v)|: d(u,v)=2\. D. Bauer, G. Fan and H.J.Veldman proved that c(G)≥ min\n,2NC2(G)\ for any 1-tough graph G with σ₃(G)≥ n≥ 3, where c(G) is the circumference of G (D. Bauer, G. Fan and H.J.Veldman,Hamiltonian properties of graphs with large neighborhood unions,Discrete Mathematics, 1991). They also conjectured a stronger upper bound for the circumference: c(G)≥min\n,2NC2(G)+4\.In this paper, we prove this conjecture.

Related

• A Fan-type condition for cycles in 1-tough and k-connected (P₂∪ kP₁)-free graphs
• A Sharp Bound for the Circumference in t-tough graphs with t>1
• Long Cycles in 1-tough Graphs
• Hamiltonian cycles in 7-tough (P₃∪ 2P₁)-free graphs
• Hamilton and long cycles in t-tough graphs with t>1