Averaging 2-rainbow domination and Roman domination

DOI10.1016/J.DAM.2016.01.021zbMATH Open1333.05213arXiv1507.04899OpenAlexW2209080201MaRDI QIDQ266967FDOQ266967

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

Publication date: 7 April 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: For a graph

G

, let

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

and

g a m m a_{R} (G)

denote the

2

-rainbow domination number and the Roman domination number, respectively. Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) proved

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

for a connected graph

G

of order

n (G)

at least

3

. Furthermore, they conjectured

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

for a connected graph

G

of minimum degree at least

2

that is distinct from

C_{5}

. We characterize all extremal graphs for their inequality and prove their conjecture.

Full work available at URL: https://arxiv.org/abs/1507.04899

Recommendations

zbMATH Keywords

rainbow domination Roman domination

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Cites Work

Cited In (7)

This page was built for publication: Averaging 2-rainbow domination and Roman domination

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