Résumé:
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.
