Notes on double Roman domination edge critical graphs
Abdelhak Omar, Ahmed Bouchou · RAIRO - Operations Research · 2025
Given a graph G = (V, E), 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) = ∑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). We say that G is γdR-edge critical, if γdR(G + e) < γdR(G) for each e ∈ E(Ḡ), where Ḡ is the complement of G, and k-γdR-edge supercritical if γdR(G) = k and γdR(G + e) = γdR(G) − 2 for every edge e ∈ E(Ḡ). In this paper, we characterize γdR-edge critical trees, answering a problem posed by Nazari-Moghaddam and Volkmann (Discrete Math. Algorithms App. 12 (2020) 2050020). Moreover, we investigate connected k-γdR-edge supercritical graphs for k ∈ {5, 6, 7, 8}.