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

Abstract

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 \le \lceil \frac{3n-g}{6}\rceil$$

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

$$\gamma (G)\le \lceil \frac{3n-g}{6}\rceil -1$$

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

$$2\gamma \le 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.