Relating 2-rainbow domination to Roman domination

DOI10.7151/DMGT.1956zbMATH Open1375.05188arXiv1512.01067OpenAlexW2963799887MaRDI QIDQ2409786FDOQ2409786

Authors: Simone Dantas, Dieter Rautenbach, José D. Alvarado

Publication date: 13 October 2017

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: For a graph

G

, let

g a m m a_{R} (G)

and

g a m m a_{r 2} (G)

denote the Roman domination number of

G

and the

2

-rainbow domination number of

G

, respectively. It is known that

g a m m a_{r 2} (G) l e q g a m m a_{R} (G) l e q f r a c 32 g a m m a_{r 2} (G)

. Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) present some kind of characterization of the graphs

G

for which

g a m m a_{R} (G) - g a m m a_{r 2} (G) = k

for some integer

k

. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer