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

B. Chaluvaraju
K. A. Vidya

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.

Full text (pdf)

• 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
• Revised: 2012-01-14.
• Accepted: 2012-04-03.