FURTHER RESULTS ON THE DOUBLE ROMAN DOMINATION IN GRAPHS

FURTHER RESULTS ON THE DOUBLE ROMAN DOMINATION IN GRAPHS

A. Omar , A. Bouchou

[PDF]

Abstract

A Roman dominating function (RDF) on a graph G is a function f : V −→ {0, 1, 2} 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 a Roman dominating function f is the value w(f) = P u∈V f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). A double Roman dominating function (DRDF) on a graph G is a function f : V −→ {0, 1, 2, 3} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 3 or two vertices v1 and v2 for which f(v1) = f(v2) = 2, and every vertex u for which f(u) = 1 is adjacent to at least one vertex v for which f(v) ≥ 2. The weight w (f) of a double Roman dominating function f is the value w(f) = P u∈V f(u). The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination number of G, denoted by γdR(G). In this paper,we characterize some classes of graphs G with γdR(G) ≥ 2 (n − Δ(G)) − 1. Moreover we provide a characterization of extremal graphs of a Nordhaus-Gaddum bound for γdR(G) improving the corresponding results given by L. Volkmann (2023). Finally, we give a characterization of graphs G with γdR(G) = 2γR(G) − 1..

Keywords

Double Roman dominating function, Double Roman domination number, Nordhaus-Gaddum inequalities, Tree.