On the rainbow domination number of graphs
Polona Repolusk
University of Maribor, Faculty of Natural Sciences and Mathematics
Janez Žerovnik
University of Ljubljana, Faculty of Mechanical Engineering
Zehui Shao
Chengdu University, School of Information Science and Technology
Meilian Liang
Guangxi University, School of Mathematics and Information Science
Chuang Yin
Guangxi Academy of Sciences
Xiaodong Xu
Guangxi Academy of Sciences
PDF
Minisymposium: GRAPH DOMINATION
Content: Given a graph $G$ and a set of $t$ colors $\lbrace 1,2,\ldots , t \rbrace$, assume that we assign an arbitrary subset of these colors to each vertex of $G$. If we require that each vertex to which an empty set is assigned has in its neighborhood all $t$ colors, then this assignment is called a $t$-rainbow dominating function of the graph $G$. The corresponding invariant $\gamma_{rt}(G)$, which is the minimum sum of numbers of assigned colors over all vertices of $G$, is called the $t$-rainbow domination number of $G$. In this talk, bounds for the $t$-rainbow domination number of an arbitrary graph will be presented. For a special case of the 3-rainbow domination numbers, bounds or exact values will be presented for several classes of graphs including paths, cycles and the generalized Petersen graphs $P(n,k)$.