Study of some roman domination parameters

Abstract

Let G = (V;E) be a simple graph. A Roman dominating function (RDF for short) on G 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 w (f) of an RDF f is de.ned as w(f) = Pu2V f(u). The minimum weight of an RDF on a graph G is called the Roman domination number of G, denoted R(G). A double Roman dominating function (DRDF) of a graph G is a function f : V ! f0; 1; 2; 3g for which the following conditions are satis.ed. i) If f(v) = 0, then the vertex v must have at least two neighbors assigned 2 under f or one neighbor assigned 3 under f. ii) If f(v) = 1, then the vertex v must have at least one neighbor u with f(u) 2. The weight w (f) of an DRDF f is the value w(f) = Pu2V f(u). The minimum weight of an DRDF on a graph G is called the double Roman domination number of G, denoted dR(G). In this thesis, we will extend the study of double Roman domination by presenting new results on the Nordhaus-Gaddum type inequality and providing a characterization of all graphs G satisfying dR (G) = 2 R (G) .. 1. We will also explore the concept of criticality, and solve some problems from various papers in this area.