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
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.
- 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
- Received: 2008-09-09.
- Revised: 2009-03-04.
- Accepted: 2009-03-10.
