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

About 13 years old · traced to

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(n−1),ρ(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)≥n≥3\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.

References

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.