General Bounds on Rainbow Domination Numbers

被引：12

作者：

Fujita, Shinya ^{[1
]}

Furuya, Michitaka ^{[2
]}

Magnant, Colton ^{[3
]}

机构：

[1] Yokohama City Univ, Int Coll Arts & Sci, Kanazawa Ku, Yokohama, Kanagawa 2360027, Japan

[2] Tokyo Univ Sci, Dept Math Informat Sci, Shinjuku Ku, Tokyo 1628601, Japan

[3] Georgia So Univ, Dept Math Sci, Statesboro, GA 30460 USA

来源：

GRAPHS AND COMBINATORICS | 2015年 / 31卷 / 03期

基金：

日本学术振兴会;

关键词：

Rainbow domination number; k-rainbow dominating function; Minimum degree;

D O I：

10.1007/s00373-013-1394-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A k-rainbow dominating function of a graph G is a function f from the vertices V(G) to such that, for all , either or . The k-rainbow domination number of a graph G is then defined to be the minimum weight of a k-rainbow dominating function. In this work, we prove sharp upper bounds on the k-rainbow domination number for all values of k. Furthermore, we also consider the problem with minimum degree restrictions on the graph.

引用

页码：601 / 613

页数：13

共 11 条

[1] [Anonymous], INT J MATH MATH SCI
[2] [Anonymous], 1962, C PUBLICATIONS
[3] Bresar B, 2008, TAIWAN J MATH, V12, P213
[4] CARO Y, 1985, ARS COMBINATORIA, V20, P167
[5] Rainbow domination on trees
Chang, Gerard J.
Wu, Jiaojiao
Zhu, Xuding
[J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (01) : 8 - 12
[6] Chartrand G., 2005, GRAPHS DIGRAPHS
[7] Haynes T.W., 1998, FUNDAMENTALS DOMINAT, DOI 10.1201/9781482246582
[8] DOMINATION IN GRAPHS WITH MINIMUM DEGREE-2
MCCUAIG, W
SHEPHERD, B
[J]. JOURNAL OF GRAPH THEORY, 1989, 13 (06) : 749 - 762
[9] Reed B., 1996, Combin. Probab. Comput., V5, P277
[10] Bounds on the 2-Rainbow Domination Number of Graphs
Wu, Yunjian
Rad, Nader Jafari
[J]. GRAPHS AND COMBINATORICS, 2013, 29 (04) : 1125 - 1133

← 1 2 →