Menu
We prove that the domination number of every graph of diameter 2 on \(n\) vertices is at most \(\left(\frac{1}{\sqrt{2}} + o(1)\right) \sqrt{n \log n}\) as \(n \to \infty\) (with logarithm of base \(e\)). This result is applied to prove that if a graph of order \(n\) has diameter 2, then it contains a spanning caterpillar whose diameter does not exceed \(\left(\frac{3}{\sqrt{2}} + o(1)\right) \sqrt{n \log n}\). These estimates are tight apart from a multiplicative constant, since there exist graphs of order \(n\) and diameter 2, with domination number not smaller than \(\left(\frac{1}{2\sqrt{2}} + o(1)\right) \sqrt{n \log n}\). In contrast, in graphs of diameter 3, the domination number can be as large as \(\lfloor \frac{n}{2} \rfloor\) (but not larger).
Our results concerning diameter 2 improve the previous upper bound of \(O(n^{3/4})\), published by Faudree et al. in [Discuss. Math. Graph Theory 15 (1995), 111-118].