The cubic edge diameter conjecture for maximum degree
Statement
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 . Here denotes the case .
Cubic edge diameter conjecture.
with equality if is one more than a prime power.
The bound is motivated by point-line incidence graphs of finite projective planes, which attain edges before a one-edge subdivision. The conjecture has been confirmed for , where , but remains open in general.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.