Relating 2-rainbow domination to Roman domination

. 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

k

, the recognition of the connected

K_{4}

-free graphs

G

with

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

is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs

G

such that

g a m m a_{r 2} (H) = g a m m a_{R} (H)

for every induced subgraph

H

of

G

, and collect several properties of the graphs

G

with

g a m m a_{R} (G) = f r a c 32 g a m m a_{r 2} (G)

.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Relating 2-rainbow domination to Roman domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409786)