Restrained Domination in Graphs with Minimum Degree Two

Abstract

Let $G=(V,E)$ be a graph. A set $S\subseteq V$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in $S$. Furthermore, a set $S\subseteq V$ is a restrained dominating set if every vertex not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V–S$. The domination number of $G$, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set, while the restrained domination number of $G$, denoted by ${\gamma }_r(G)$, is the minimum cardinality of a restrained dominating set of $G$.
We show that if a connected graph $G$ of order $n$ has minimum degree at least $2$ and is not one of eight exceptional graphs, then ${\gamma }_r(G)\le (n–1)/2$. We show that if $G$ is a graph of order $n$ with $\delta =\delta (G)\ge 2$, then ${\gamma }_r(G)\le n(1+(\frac{1}{\delta }{)}^{\frac{\delta }{\delta -1}}–(\frac{1}{\delta }{)}^{\frac{1}{\delta -1}})$.