Logo
All Random Solved Random Open
OPEN
For a triangle-free graph $G$ let $h_2(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $2$. Is it true that if $G$ has maximum degree $o(n^{1/2})$ then $h(G)=o(n^2)$?
A problem of Erdős, Gyárfás, and Ruszinkó [EGR98]. Simonovits showed that there exist graphs $G$ with maximum degree $\gg n^{1/2}$ and $h_2(G)\gg n^2$.

Erdős, Gyárfás, and Ruszinkó [EGR98] proved that if $G$ has no isolated vertices and maximum degree $O(1)$ then $h_2(G)\ll n\log n$.

See also [619].