For a graph G, let gamma(r2)(G) and gamma(R)(G) denote the 2-rainbow domination number and the Roman domination number, respectively. Fujita and Furuya (2013) proved gamma(r2)(G) + gamma(R)(G) <= 6/4n(G) for a connected graph G of order n(G) at least 3. Furthermore, they conjectured gamma(r2)(G) + gamma(R)(G) <= 4/3n(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. (C) 2016 Elsevier B.V. All rights reserved.
展开▼
