Some Upper Bounds for the Domination Number

Abstract

Let $G$ be a graph of order $n(G)$, minimum degree $\delta (G)$, diameter $d_m(G)$, and let $\overline{G}$ be the complement of the graph $G$. A vertex set $D$ is called a dominating set of $G$, if each vertex not in $D$ has at least one neighbor in $D$. The domination number $\gamma (G)$ equals the minimum cardinality of a dominating set of $G$.
In this article we show the inequalities

1. $\gamma (G)\le \lfloor \frac{n(G)}{3}\rfloor ,\text{ if }\delta (G)\ge 7,$
2. $\gamma (G)+\gamma (\overline{G})\le \lfloor \frac{n(G)}{3}\rfloor +2,\text{ if }\delta (G),\delta (\overline{G})\ge 7,\text{ and}$
3. $\gamma (G)\le \lceil \frac{n(G)}{4}\rceil +1,\text{ if }\text{dm}(G)=2.$

Using the concept of connectivity, we present some related upper bounds for the domination number of graphs with $\text{dm}(G)=2$ and $\text{dm}(G)=3$.