Graphs of diameter 3 with the minimum number of edges (Q2639069)

For integers \(n\geq D\geq a\geq 1,\) let \({\mathcal P}(n,D,a)\) denote the class of connected graphs with n vertices such that there is a complete subgraph \(K_ a\), the remaining vertices have degree 1, and the maximum degree is at most D. Such graphs, which have \(n-1+\binom{a-1}{2}\) edges and diameter at most 3, are called porcupines. The author proves the following result. Let \(n>D\geq \sqrt{48n}/3-2\) and let a be the minimum integer that satisfies \(n+a^ 2\leq a(D+2).\) If G is a graph of order n, diameter at most 3, and maximum degree at most D, then G has at least \(n- 1+\binom{a-1}{2}\) edges. Also, for \(D\neq n-1\) and \(d\neq (n-1)/2,\) G has precisely \(n-1+\binom{a-1}{2}\) edges if and only if \(G\in {\mathcal P}(n,D,a).\) This answers an extremal question of Bollobas and verifies that porcupines have the minimum number of edges for graphs of diameter at most 3.