Bauer–Fan–Veldman circumference conjecture for 1-tough graphs

Let GG be a graph of order nn, let τ(G)\tau(G) denote its toughness, let ρ(G)\rho(G) denote the independence number, and let σ3(G)\sigma_3(G) be its smallest union degree of order 33:

σ3(G)={min{deg(v1)+deg(v2)+deg(v3):{v1,v2,v3} is independent},ρ(G)3,3(n1),ρ(G)<3.\sigma_3(G)=\begin{cases}\min\{\deg(v_1)+\deg(v_2)+\deg(v_3):\{v_1,v_2,v_3\}\text{ is independent}\},&\rho(G)\geq 3,\\3(n-1),&\rho(G)<3.\end{cases}

For nonadjacent vertices u,vu,v at distance 22, write N(u,v)=N(u)N(v)N(u,v)=N(u)\cup N(v), and define

NC2(G)={min{N(u)N(v):d(u,v)=2},G is not complete, 1,G is complete.NC2(G)=\begin{cases}\min\{|N(u)\cup N(v)|:d(u,v)=2\},&G\text{ is not complete},\ -1,&G\text{ is complete}.\end{cases}

Let c(G)c(G) be the circumference of GG, namely the length of a longest cycle. Bauer–Fan–Veldman conjecture. If GG is a 1-tough graph with σ3(G)n3\sigma_3(G)\geq n\geq 3, then

c(G)min{n,2NC2(G)+4}.c(G)\geq\min\{n,2NC2(G)+4\}.

This strengthens the earlier lower bound c(G)min{n,2NC2(G)}c(G)\geq\min\{n,2NC2(G)\}; the intermediate bound with additive constant 22 follows from a theorem of Hoa. The conjecture is the claim proved in the source paper.

Sources & referencesView supporting material

Primary source

Tri Lai, “Proof of a conjecture of Bauer, Fan and Veldman”, arXiv:1309.5379 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.