On the rainbow domination number of graphs

Polona Repolusk University of Maribor, Faculty of Natural Sciences and Mathematics

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

Back to all abstracts