Hits:

Indexed by:期刊论文

Date of Publication:2009-04-28

Journal:DISCRETE APPLIED MATHEMATICS

Included Journals:SCIE、EI、Scopus

Volume:157

Issue:8

Page Number:1932-1937

ISSN No.:0166-218X

Key Words:Domination; 2-rainbow domination; Generalized Petersen graph

Abstract:Assume we have a set of k colors and we assign an arbitrary subset of these colors to each vertex of a graph G. If we require that each vertex to which an empty set is assigned has in its neighborhood all k colors, then this assignment is called the k-rainbow dominating function of a graph G. The corresponding invariant gamma(rk)(G), which is the minimum sum of numbers of assigned colors over all vertices of G, is called the k-rainbow domination number of G. Bresar and Sumenjak [B. Bregar, T.K. Sumenjak On the 2-rainbow domination in graphs, Discrete Applied Mathematics, 155 (2007) 2394-2400] showed that [4n/5] <= gamma(r2)(P(n, 2)) <= [4n/5] + alpha, where alpha = 0 for n  3, 9 mod 10 and alpha = 1 for n  1. 5, 7 mod 10. And they raised the question: IS gamma(r2)(P(2k + 1, k)) = 2k + 1 for all k >= 2? In this paper, we put forward the answer to the question. More over, we show that gamma(r2)(P(n, 2)) = [4n/5] + alpha, where alpha = 0 for n  0, 3, 4, 9 mod 10 and alpha = 1 for n  1, 2, 5, 6, 7, 8 mod 10. (C) 2009 Elsevier B.V. All rights reserved.