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 \leq {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 \leq n – \delta\]

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