On maximal Roman domination in graphs. Issue 7 (2nd July 2016) - Abdollahzadeh Ahangar, Hossein; Chellali, Mustapha; Kuziak, Dorota; Samodivkin, Vladimir
Abstract : A Roman dominating function (RDF) for a graph G = ( V, E ) is a function f : V → 0, 1, 2 satisfying the condition that every vertex u of G for which f ( u ) = 0 is adjacent to at least one vertex v of G for which f ( v ) = 2 . The weight of a RDF f is the sum f ( V ) = ∑ v ∈ V f ( v ), and the minimum weight of a RDF for G is the Roman domination number, γ R ( G ), of G . A maximal RDF for a graph G is a RDF f such that V 0 = w ∈ V | f ( w ) = 0 is not a dominating set of G . The maximal Roman domination number, γ m R ( G ), of a graph G equals the minimum weight of a maximal RDF for G . We first show that determining the number γ m R ( G ) for an arbitrary graph G is NP-complete even when restricted to bipartite or planar graphs. Then, we characterize connected graphs G such that γ m R ( G ) = γ R ( G ) . We also provide a characterization of all trees T of order n such that γ m R ( T ) = n − 2 .