Some Remarks on Lower Bounds on the \(p\)-Domination Number in Trees

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) \geq \frac{(p-1)n(T) + 1}{p}$$

The special case \( p = 2 \) of this inequality easily leads to

$$\gamma_2(T) \geq \beta(T) + 1 \geq \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) = \left\lceil \frac{(p-1)n(T) + 1}{p} \right\rceil \) as well as all non-trivial trees \( T \) with \( \gamma_2(T) = \gamma(T) + 1 \) and \( \gamma_2(T) = \beta(T) + 1 \).