Opuscula Math. 32, no. 4 (), 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.