On the 2-rainbow domination in graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Boš ; tjan Breš ; ar ; Tadeja Kraner Š ; umenjak
• 关键词：Complexity ; NP-completeness ; Domination ; Cartesian product ; Generalized Petersen graph
• 刊名：Discrete Applied Mathematics
• 出版年：2007
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：15 October 2007
• 卷：155
• 期：17
• 页码：2394-2400
• 文件大小：160 K

摘要

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. 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.