On maximal Roman domination in graphs. Issue 7 (2nd July 2016)

• Record Type: Journal Article
• Authors: Abdollahzadeh Ahangar, Hossein; Chellali, Mustapha; Kuziak, Dorota; Samodivkin, Vladimir
• Is Part Of: International journal of computer mathematics. Volume 93:Issue 7(2016)
• Page Start: 1093
• Page End: 1102
• Publication Date: 2016-07-02
• Subjects: maximal Roman domination -- Roman domination; 05C69; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2015.1052804
• Languages: English
• ISSNs: 0020-7160

Abstract

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 .