| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420917 | Discrete Applied Mathematics | 2007 | 7 Pages |
Abstract
The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K2G□K2. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k)GP(n,k) this number is between ⌈4n/5⌉⌈4n/5⌉ and n with both bounds being sharp.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Boštjan Brešar, Tadeja Kraner Šumenjak,