Logo
All Random Solved Random Open
OPEN
For a triangle-free graph $G$ let $h_r(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $r$.

Is it true that there exists a constant $c>0$ such that if $G$ is connected then $h_4(G)<(1-c)n$?

A problem of Erdős, Gyárfás, and Ruszinkó [EGR98] who proved that $h_3(G)\leq n$ and $h_5(G) \leq \frac{n-1}{2}$ and there exist connected graphs $G$ on $n$ vertices with $h_3(G)\geq n-c$ for some constant $c>0$.

See also [134] and [618].