Relating Pairs of Distance Domination Parameters

Abstract

Let $n\ge 1$ be an integer and let $G$ be a graph of order $p$. A set $\mathcal{D}$ of vertices of $G$ is an $n$-dominating set (total $n$-dominating) set of $G$ if every vertex of $V(G)–\mathcal{D}$ ($V(G)$, respectively) is within distance $n$ from some vertex of $\mathcal{D}$ other than itself. The minimum cardinality among all $n$-dominating sets (respectively, total $n$-dominating sets) of $G$ is called the $n$-domination number (respectively, total $n$-domination number) and is denoted by ${\gamma }_n(G)$ (respectively, ${\gamma }_n^t(G)$). A set $\mathcal{I}$ of vertices of $G$ is $n$-independent if the distance (in $G$) between every pair of distinct vertices of $\mathcal{I}$ is at least $n+1$. The minimum cardinality among all maximal $n$-independent sets of $G$ is called the $n$-independence number of $G$ and is denoted by $i_n(G)$. Suppose ${\mathcal{I}}_k$ is an $n$-independent set of $k$ vertices of $G$ for which there exists a vertex $v$ of $G$ that is within distance $n$ from every vertex of ${\mathcal{I}}_k$. Then a connected subgraph of minimum size that contains the vertices of ${\mathcal{I}}_k\cup \{v\}$ is called an $n$-generalized $K_{1,k}$ in $G$. It is shown that if $G$ contains no $n$-generalized $K_{1,3}$, then ${\gamma }_n(G)=i_n(G)$. Further, it is shown if $G$ contains no $n$-generalized $K_{1,k+1}$, $k\ge 2$, then $i_n(G)\le (k-1){\gamma }_n(G)–(k-2)$. It is shown that if $G$ is a connected graph with at least $n+1$ vertices, then there exists a minimum $n$-dominating set $\mathcal{D}$ of $G$ such that for each $d\in \mathcal{D}$, there exists a vertex $v\in V(G)–\mathcal{D}$ at distance $n$ from $d$ and distance at least $n+1$ from every vertex of $\mathcal{D}–\{d\}$. Using this result, it is shown if $G$ is a connected graph on $p\ge 2n+1$ vertices, then ${\gamma }_n(G)\le p/(n+1)$ and that $i_n(G)+n{\gamma }_n(G)\le p$. Finally, it is shown that if $T$ is a tree on $p\ge 2n+1$ vertices, then $i_n(G)+n{\gamma }_n^t(G)\le p$.