Domination Number of Graphs with Bounded Diameter

Abstract

We prove that the domination number of every graph of diameter 2 on $n$ vertices is at most $(\frac{1}{\sqrt{2}}+o(1))\sqrt{n\log n}$ as $n\to \mathrm{\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 $(\frac{3}{\sqrt{2}}+o(1))\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 $(\frac{1}{2\sqrt{2}}+o(1))\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].