Journal of the
Korean Mathematical Society JKMS

A dominating set for a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ not in $D$ is adjacent to a vertex of $D$. Reed [11] considered the domination problem for graphs with minimum degree at least three. He showed that any graph $G$ of minimum degree at least three contains a dominating set $D$ of size at most $\frac{3}{8}|V(G)|$ by introducing a covering by vertex disjoint paths. In this paper, by using this technique, we show that every graph on $n$ vertices of minimum degree at least four contains a dominating set $D$ of size at most $\frac{4}{11}|V(G)|$.

Keywords: graphs, domination number

MSC numbers: 05C50, 05C69