Roman {2}-domination

In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G=(V,E), a Roman {2}-dominating function f:V→{0,1,2} has the property that for every vertex v∈V with f(v)=0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to least two vertices assign...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2016-05, Vol.204, p.22-28
Main Authors: Chellali, Mustapha, Haynes, Teresa W., Hedetniemi, Stephen T., McRae, Alice A.
Format: Article
Language:English
Subjects:
2-domination
2-rainbow domination
Functions (mathematics)
Graph theory
Graphs
Mathematical analysis
Minimum weight
Roman
Roman [formula omitted]-domination
Roman domination
Trees
Weak Roman domination
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G=(V,E), a Roman {2}-dominating function f:V→{0,1,2} has the property that for every vertex v∈V with f(v)=0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to least two vertices assigned 1 under f. The weight of a Roman {2}-dominating function is the sum ∑v∈Vf(v), and the minimum weight of a Roman {2}-dominating function f is the Roman {2}-domination number. First, we present bounds relating the Roman {2}-domination number to some other domination parameters. In particular, we show that the Roman {2}-domination number is bounded above by the 2-rainbow domination number. Moreover, we prove that equality between these two parameters holds for trees and cactus graphs with no even cycles. Finally, we show that associated decision problem for Roman {2}-domination is NP-complete, even for bipartite graphs.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2015.11.013