Best possible upper bounds on the restrained domination number of cubic graphs

A dominating set in a graph G $G$ is a set S $S$ of vertices such that every vertex in V(G)⧹S $V(G)\setminus S$ is adjacent to a vertex in S $S$. A restrained dominating set of G $G$ is a dominating set S $S$ with the additional restraint that the graph G-S $G-S$ obtained by removing all vertices in S $S$ is isolate-free. The domination number gamma(G) $\gamma (G)$ and the restrained domination number gamma r(G) ${\gamma }_{r}(G)$ are the minimum cardinalities of a dominating set and restrained dominating set, respectively, of G $G$. Let G $G$ be a cubic graph of order n $n$. A classical result of Reed states that gamma(G)<= 38n $\gamma (G)\le \frac{3}{8}n$, and this bound is best possible. To determine the best possible upper bound on the restrained domination number of G $G$ is more challenging, and we prove that gamma r(G)<= 25n ${\gamma }_{r}(G)\le \frac{2}{5}n$.