Bounds on an Independent Distance Domination Parameter

Abstract

Let $m\ge 1$ be an integer and let $G$ be a graph of order $n$. A set $\mathcal{D}$ of vertices of $G$ is an $m$-dominating set of $G$ if every vertex of $V(G)–\mathcal{D}$ is within distance $m$ from some vertex of $\mathcal{D}$. An independent set of vertices of $G$ is a set of vertices of $G$ whose elements are pairwise nonadjacent. The minimum cardinality among all independent $m$-dominating sets of $G$ is called the independent $m$-domination number and is denoted by $id(m,G)$. We show that if $G$ is a connected graph of order $n\ge m+1$, then $id(m,G)\le (n+m+1-2\sqrt{n}/m),$ and this bound is sharp.