Some Remarks on Lower Bounds on the $p$-Domination Number in Trees

Abstract

Let $G$ be a simple graph, and let $p$ be a positive integer. A subset $D\subseteq V(G)$ is a $p$-\emph{dominating} set of the graph $G$, if every vertex $v\in V(G)–D$ is adjacent to at least $p$ vertices of $D$. The $p$-domination number ${\gamma }_p(G)$ is the minimum cardinality among the $p$-dominating sets of $G$. Note that the $1$-domination number ${\gamma }_1(G)$ is the usual domination number $\gamma (G)$. The covering number of a graph $G$ is denoted by $\beta (G)$. If $T$ is a tree of order $n(T)$, then Fink and Jacobson [1] proved in 1985 that

$${\gamma }_p(T)\ge \frac{(p-1)n(T)+1}{p}$$

The special case $p=2$ of this inequality easily leads to

$${\gamma }_2(T)\ge \beta (T)+1\ge \gamma (T)+1$$

for every non-trivial tree $T$. Inspired by the article of Fink and Jacobson [1], we characterize in this paper the family of trees $T$ with ${\gamma }_p(T)=\lceil \frac{(p-1)n(T)+1}{p}\rceil$ as well as all non-trivial trees $T$ with ${\gamma }_2(T)=\gamma (T)+1$ and ${\gamma }_2(T)=\beta (T)+1$.