Upper Bounds on the Domination Number of a Graph in Terms of Order and Minimum Degree

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 1975, Payan $[6]$ communicated without proof the inequality
$$2\gamma \le n+1–\delta$$
for every connected graph not isomorphic to the complement of a one-regular graph, where $n$ is the order and $\delta$ the minimum degree of the graph. A first proof of (*) was published by Flach and Volkman $[3]$ in $1980$.

In this paper, we firstly present a more transparent proof of (*). Using the idea of this proof, we show that

$$2\gamma \le n–\delta$$

for connected graphs with exception of well-determined families of graphs.