Bounds on perfect k-domination in trees: an algorithmic approach
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AGH Univeristy of Science and Technology Press
2012-01-01
|
| Series: | Opuscula Mathematica |
| Subjects: | |
| Online Access: | http://www.opuscula.agh.edu.pl/vol32/4/art/opuscula_math_3249.pdf |
| Summary: | 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. |
|---|---|
| ISSN: | 1232-9274 |