algorithmic aspects of roman graphs

Let g = (v, e) be a graph. a set s ⊆ v is called a dominating set of g if for every v ∈ v s there is at least one vertex u ∈ n(v) such that u ∈ s. the domination number of g, denoted by γ(g), is equal to the minimum cardinality of a dominating set in g. a roman dominating function (rdf) on g is a function f : v → {0, 1, 2} such that every vertex v ∈ v with f(v) = 0 is adjacent to at least one vertex u with f(u) = 2. the weight of f is the sum f(v ) = ∑ v∈v f(v). the minimum weight of a rdf on g is the roman domination number of g, denoted by γr(g). a graph g is a roman graph if γr(g) = 2γ(g). in this paper, we first study the complexity issue of the problem posed in [e. j. cockayane, p. m. dreyer jr., s. m. hedetniemi and s. t. hedetniemi, on roman domination in graphs, discrete math. 278 (2004), 11–22], and show that the problem of deciding whether a given graph is a roman graph is np-hard even when restricted to chordal graphs. then, we give linear algorithms that compute the domination number and the roman domination number of a given unicyclic graph. finally, using these algorithms we give a linear algorithm that decides whether a given unicyclic graph is a roman graph.