The asymptotic upper-bound conjecture for edge diameter
The asymptotic upper-bound conjecture for edge diameter
Let be the smallest integer such that every graph with edges and maximum degree at most contains two edges whose distance is at least ; equivalently, is the largest number of edges in a graph of maximum degree at most whose line graph has diameter at most . The parameter is fixed.
Asymptotic upper-bound conjecture. For and any ,
for all sufficiently large .
This is the complementary challenge to the asymptotic lower bound and would identify the asymptotic value of up to a factor tending to one. The paper states that the conjecture remains open for the relevant values of , while the case is excluded because its known leading constant is rather than .
Sources & referencesView supporting material
Primary source
Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos and Ross J. Kang, “Maximising line subgraphs of diameter at most t”, arXiv:2103.11898 (2021).
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.