On the computational complexity of Roman domination parameters in graph

Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=116850
Date :  2016/08/15
Publish in :    Graphs and Groups, Spectra and Symmetries (G2S2)


Keywords :

Abstract :

---

A Roman dominating function (or just RDF) on a graph G = (V;E) is a function f : V 􀀀 f0; 1; 2g satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = P u2V (G) f(u). An RDF f can be represented as f = (V0; V1; V2), where Vi = fv 2 V : f(v) = ig for i = 0; 1; 2. The Roman domination number, R(G), of G is the minimum weight of an RDF on G. Several parameters related to the Roman dominating functions have been considered in the very recent years, for example, Roman bondage number, Roman reinforcement number, total Roman domination number, multiple Roman domination number, paired Roman domination number, and etc. We rst establish several bounds for the Roman domination number of a graph under some given properties of the graph. We then determine the computational complexity of several Roman domination parameters, and show that the decision problem for these parameters are NP-complete even when restricted to bipartite graphs or chordal graphs. We also study Roman domination parameters in Random graphs.