The -rainbow reinforcement numbers in graphs

详细信息    查看全文

• 作者：J. Amjadi^a ; ^{j-amjadi@azaruniv.edu} ; L. Asgharsharghi^a ; ^{l.sharghi@azaruniv.edu} ; N. Dehgardi^b ; ^{ndehgardi@gmail.com} ; M. Furuya^c ; ^{michitaka.furuya@gmail.com} ; S.M. Sheikholeslami^a ; ^{s.m.sheikholeslami@azaruniv.edu} ; L. Volkmann^d ; ^{volkm@math2.rwth-aachen.de}
• 关键词：kk-rainbow dominating function ; kk-rainbow domination number ; kk-rainbow reinforcement number
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P3
• 页码：394-404
• 全文大小：449 K
• 卷排序：217

文摘

Let k≥1k≥1 be an integer, and let GG be a graph. A kk-rainbow dominating function   (or a kk-RDF  ) of GG is a function ff from the vertex set V(G)V(G) to the family of all subsets of {1,2,…,k}{1,2,…,k} such that for every v∈V(G)v∈V(G) with f(v)=0̸f(v)=0̸, the condition ⋃_{u∈NG(v)f(u)={1,2,…,k}⋃u∈NG(v)f(u)={1,2,…,k} is fulfilled, where NG(v)NG(v) is the open neighborhood of vv. The weight   of a kk-RDF ff of GG is the value ω(f)=∑v∈V(G)∣f(v)∣ω(f)=∑v∈V(G)∣f(v)∣. The kk-rainbow domination number   of GG, denoted by γrk(G)γrk(G), is the minimum weight of a kk-RDF of GG. The 11-rainbow domination is the same as the classical domination.The kk-rainbow reinforcement number   of GG, denoted by rrk(G)rrk(G), is the minimum number of edges that must be added to GG in order to decrease the kk-rainbow domination number. In this paper, we study the kk-rainbow reinforcement number of graphs to compare γrkγrk and γrk′γrk′ for k≠k′k≠k′, and present some sharp bounds concerning the invariant.}