On a Relationship between $2$-dominating and $5$-dominating sets in Graphs

Abstract

In a graph, a set $D$ is an $n$-dominating set if for every vertex $x$, not in $D$, $x$ is adjacent to at least $n$ vertices of $D$. The $n$-domination number, ${\gamma }_n(G)$, is the order of a smallest $n$-dominating set. When this concept was first introduced by Fink and Jacobson, they asked whether there existed a function $f(n)$, such that if $G$ is any graph with minimum degree at least $n$, then ${\gamma }_n(G)<{\gamma }_{f(n)}(G)$. In this paper we show that ${\gamma }_2(G)<{\gamma }_5(G)$ for all graphs with minimum degree at least $2$. Further, this result is best possible in the sense that there exist infinitely many graphs $G$ with minimum degree at least $2$ having ${\gamma }_2(G)={\gamma }_4(G)$.