Some bounds on the \(p\)-domination number in trees (Q2501539)

For a positive integer \(p\) and a graph \(G=(V,E)\), a subset \(S\) of \(V\) is called a \(p\)-dominating set, if every vertex of \(V\setminus S\) is dominated at least \(p\) times; and \(S\) is called a \(p\)-dependent set if the subgraph of \(G\) induced by the vertices of \(S\) has maximum degree at most \(p-1\). The maximum cardinality of a \(p\)-dominating set of \(G\) is called the \(p\)-domination number \(\gamma_p(G)\), and the maximum cardinality of a \(p\)-dependent set of \(G\) is called the \(p\)-dependence number \(\beta_p(G)\). The paper shows that for \(p\geq 2 \) and a bipartite graph \(G\), \(\gamma_p(G)\) is bounded above by \((| V| +| Y_p| )/2\), where \(Y_p\) is the set of vertices in \(G\) of degree at most \(p-1\); and for every tree \(T\) \(\gamma_p(T)\) is bounded below by \(\beta_{p-1} (T)\). Trees achieving equality in both bounds are characterized.