An Upper Bound for the Domination Number of a Graph in Terms of Order 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 (G)\le \lceil \frac{3n-g}{6}\rceil$$

for each graph $G$ of order $n$, minimum degree $\delta \ge 2$, and girth $g\ge 5$. For this class of graphs, Volkmann [8] recently gave the better bound

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

if $G$ is neither a cycle nor one of two exceptional graphs. If $G$ is a graph of order $n$, minimum degree $\delta \ge 2$, girth $g\ge 5$, then we show in this paper that

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

if $G$ is neither a cycle nor one of 40 exceptional graphs of order between 8 and 21.