Upper Bounds on the Domination Number of a Graph in Terms of Diameter and Girth

A vertex set \( D \) of a graph \( G \) is a dominating set if every vertex not in \( D \) is adjacent to some vertex in \( D \). The domination number \( \gamma \) of a graph \( G \) is the minimum cardinality of a dominating set in \( G \). In 1989, Brigham and Dutton [1] proved

\[\gamma \leq \left\lceil\frac{3n-g}{6}\right\rceil\]

for each graph \( G \) of order \( n \), minimum degree \( \delta \geq 2 \), and girth \( g \geq 5 \). If \( G \) is a graph of order \( n \), minimum degree \( \delta \geq 2 \), girth \( g \geq 5 \) and neither a cycle nor one of two exceptional graphs, then we give in this paper the better bound

\[\gamma(G) \leq \left\lceil\frac{3n-g}{6}\right\rceil-1\]

For \( \delta \geq 3 \) and \( g \geq 5 \), we also prove \( \gamma \leq \left\lceil\frac{6n-g}{15}\right\rceil \), and this inequality is better than \( (*) \) when \( n > g + 10 \). In addition, if \( \delta \geq 3 \), then we show that

\[2\gamma \leq n – (\delta-2)(1 + \lfloor{d}/{3}\rfloor)\]

where \( d \) is the diameter of the graph. Some related bounds in terms of the diameter, girth, order, and minimum degree are also presented.