Opuscula Math. 32, no. 4 (2012), 707-714
http://dx.doi.org/10.7494/OpMath.2012.32.4.707
Opuscula Mathematica
Bounds on perfect k-domination in trees: an algorithmic approach
Abstract. Let \(k\) be a positive integer and \(G = (V;E)\) be a graph. A vertex subset \(D\) of a graph \(G\) is called a perfect \(k\)-dominating set of \(G\) if every vertex \(v\) of \(G\) not in \(D\) is adjacent to exactly \(k\) vertices of \(D\). The minimum cardinality of a perfect \(k\)-dominating set of \(G\) is the perfect \(k\)-domination number \(\gamma_{kp}(G)\). In this paper, a sharp bound for \(\gamma_{kp}(T)\) is obtained where \(T\) is a tree.
Keywords: \(k\)-domination, perfect domination, perfect \(k\)-domination.
Mathematics Subject Classification: 05C69, 05C70.
- B. Chaluvaraju
- Department of Mathematics, Bangalore University, Central College Campus, Bangalore -560 001, India
- K. A. Vidya
- Department of Mathematics, Bangalore University, Central College Campus, Bangalore -560 001, India
- Received: 2010-09-27.
- Revised: 2012-01-14.
- Accepted: 2012-04-03.
