Bauer–Fan–Veldman circumference conjecture for 1-tough graphs
Bauer–Fan–Veldman circumference conjecture for 1-tough graphs
Let be a graph of order , let denote its toughness, let denote the independence number, and let be its smallest union degree of order :
For nonadjacent vertices at distance , write , and define
Let be the circumference of , namely the length of a longest cycle. Bauer–Fan–Veldman conjecture. If is a 1-tough graph with , then
This strengthens the earlier lower bound ; the intermediate bound with additive constant 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.