A note on the p-domination number of trees

Abstract

Let $p$ be a positive integer and $G=(V(G),E(G))$ a graph. A $p$-dominating set of $G$ is a subset $S$ of $V(G)$ such that every vertex not in $S$ is dominated by at least $p$ vertices in $S$. The $p$-domination number $\gamma_p(G)$ is the minimum cardinality among the p-dominating sets of $G$. Let $T$ be a tree with order $n \geq 2$ and $p \geq 2$ a positive integer. A vertex of $V(T)$ is a $p$-leaf if it has degree at most $p - 1$, while a $p$-support vertex is a vertex of degree at least $p$ adjacent to a $p$-leaf. In this note, we show that $\gamma_p(T) \geq (n + |L_p(T)|-|S_p(T)|)/2$, where $L_{p}(T)$ and $S_{p}(T)$ are the sets of $p$-leaves and $p$-support vertices of $T$, respectively. Moreover, we characterize all trees attaining this lower bound.