How to decrease the diameter of triangle-free graphs (Q1307443)

If \(G\) is a triangle-free graph let \(h_d(G)\) be the minimum number of edges one has to add to get a triangle-free graph of diameter at most \(d\). If \(G\) has no isolated vertices and has maximum degree \(D\) then \(c_1(D)n\log n\leq h_2(G) \leq c_2(D) n \log n\). The following very nice result is proved. The maximum of \(h_2(G)\) over all graphs on \(n\geq n_0\) vertices is \(\lfloor {n\over 2} -1 \rfloor \lceil {n\over 2} -1 \rceil\). \(h_3(G)\leq n-1\) and \(h_5(G)\leq {{n-1}\over 2}\). But \(h_4(G)\leq (1-\varepsilon)n\) with some \(\varepsilon>0\) is only conjectured.