On the 2-rainbow domination in graphs |
| |
| Authors: | Boštjan Brešar Tadeja Kraner Šumenjak |
| |
| Institution: | a FEECS, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia
b FA, University of Maribor, Vrbanska 30, 2000 Maribor, Slovenia |
| |
| Abstract: | The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□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) this number is between ⌈4n/5⌉ and n with both bounds being sharp. |
| |
| Keywords: | 05C85 05C69 |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
