Find in Library

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.