Domination, Independent Domination and $k$-independence in Trees

Source abstract

For a graph $G$, denote its domination number and independent domination number by $\gamma(G)$ and $i(G)$. For a positive integer $k$, a subset $S \subseteq V(G)$ is a $k$-independent set of $G$ if $\Delta(G[S]) \lt k$. The $k$-independence number $\alpha_{k}(G)$ is the cardinality of a maximum $k$-independent set of $G$. In this paper, we prove that for any nontrivial tree $T$, $i(T) \leq \frac{k+1}{2k} \alpha_{k}(T)$ and $\gamma(T) \leq \frac{k}{2k-1} \alpha_{k}(T)$, respectively. This extends the recent result for $k = 2$ by Dehgardi et al. Both bounds are best possible and the extremal trees are characterized.