On rainbow domination of cubic graphs

Abstract

The structure of minimal weight rainbow domination functions of cubic graphs are studied. Based on general observations for cubic graphs, generalized Petersen graphs $P(ck,k)$ are characterized whose 4- and 5-rainbow domination numbers equal the general lower bounds. As $t$-rainbow domination of cubic graphs for $t\ge 6$ is trivial, characterizations of such generalized Petersen graphs $P(ck,k)$ are known for all $t$-rainbow domination numbers.In addition, new upper bounds for 4- and 5-rainbow domination numbers that are valid for all $P(ck,k)$ are provided.

arXiv comment11 pages, 1 fig