Concerning the number of edges in a graph with diameter constraints (Q2721331)

The authors study several problems related to the number of edges of a graph with diameter constraints, e.g. the following problem: Let \(k\geq 2\) be an integer. Given a graph \(G\) of diameter \(k\) find a spanning graph \(H\) of \(G\) of diameter \(k\) of minimum size. The authors show that this problem is NP-hard. Moreover, they give four efficient heuristics for this problem for \(k=2\). They also conjecture that the number of edges in a critical graph of diameter \(2\) with \(n\) vertices is at most \(\Delta(n-\Delta)\), where \(\Delta\) is the maximum degree.