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



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)$.

Back to all abstracts