Opuscula Math. 29, no. 2 (2009), 157-164
http://dx.doi.org/10.7494/OpMath.2009.29.2.157

Opuscula Mathematica

# A note on the p-domination number of trees

You Lu
Xinmin Hou
Jun-Ming Xu

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.

Keywords: $$p$$-domination number, trees.

Mathematics Subject Classification: 05C69.

Full text (pdf)

• You Lu
• University of Science and Technology of China, Department of Mathematics, Hefei, Anhui, 230026, China
• Xinmin Hou
• University of Science and Technology of China, Department of Mathematics, Hefei, Anhui, 230026, China
• Jun-Ming Xu
• University of Science and Technology of China, Department of Mathematics, Hefei, Anhui, 230026, China
• Revised: 2009-03-04.
• Accepted: 2009-03-10.