Recent Bounds on Domination Parameters

Abstract

In this paper, we survey some recent bounds on domination parameters. A characterisation of connected graphs with minimum degree at least 2 and domination number exceeding a third their size is obtained. Upper bounds on the total domination number, ${\gamma }_t(G)$, of a graph $G$ in terms of its order and size are established. If $G$ is a connected graph of order $n$ with minimum degree at least 2, then either ${\gamma }_t(G)\le 4n/7$ or $G\in \{C_3,C_5,C_6,C_{10}\}$. A characterisation of those graphs of order $n$ which are edge-minimal with respect to satisfying $G$ connected, $\delta (G)\ge 2$, and $\gamma (G)\ge 4n/7$ is obtained. We establish that if $G$ is a connected graph of size $q$ with minimum degree at least 2, then ${\gamma }_t(G)\le (q+2)/2$. Connected graphs $G$ of size $q$ with minimum degree at least 2 satisfying ${\gamma }_t(G)>q/2$ are characterised. Upper bounds on other domination parameters, including the strong domination number and the restrained domination number are presented. We provide a constructive characterisation of those trees with equal domination and restrained domination numbers. A constructive characterisation of those trees with equal domination and weak domination numbers is also obtained.