Some bounds on the p-domination number in trees

Let p be a positive integer and G = (V, E) a graph. A subset S of V is a p-dominating set if every vertex of V - S is dominated at least p times, and S is a p-dependent set of G if the subgraph induced by the vertices of S has maximum degree at most p - 1. The minimum cardinality, of a p-dominating set a of G is the p-domination number gamma(p) (G) and the maximum cardinality of a p-dependent set of G is the p-dependence number beta(p) (G). For every positive integer p >= 2, we show that for a bipartite graph G, gamma(p) (G) is bounded above by (vertical bar V vertical bar + vertical bar Y-p vertical bar)/2, where Y-p is the set of vertices of G of degree at most p - 1, and for every tree T, gamma(p)(T) is bounded below by beta(p-1)(T). Moreover, we characterize the trees achieving equality in each bound. (c) 2006 Elsevier B.V. All rights reserved.