Proof of a conjecture of Bauer, Fan and Veldman

preprint2013arXivOpen access

Abstract

For a 1-tough graph GG we define σ3(G)=min⁡{°(u)+°(v)+°(w):σ_3(G) = \min\{°(u) + °(v)+ °(w): {u,v,w}\{u, v, w\} is an independent set of vertices}\} and NC2(G)=min⁡{∣N(u)∪N(v)∣:d(u,v)=2}NC2(G)=\min \{|N(u)\cup N(v)|: d(u,v)=2\}. D. Bauer, G. Fan and H.J.Veldman proved that c(G)≥min⁡{n,2NC2(G)}c(G)\geq \min\{n,2NC2(G)\} for any 1-tough graph GG with σ3(G)≥n≥3σ_3(G)\geq n\geq 3, where c(G)c(G) is the circumference of GG (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}c(G)\geq\min\{n,2NC2(G)+4\}.In this paper, we prove this conjecture.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.