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.