Notes on double Roman domination edge critical graphs

¹ LAMDA-RO Laboratory, Department of Mathematics, University of Blida 1, Blida, Algeria
² University of Médéa, Médéa, Algeria

^* Corresponding author: omar_abdelhak@univ-blida.dz

Received: 8 April 2023
Accepted: 13 February 2025

Abstract

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 v₁ and v₂ for which f(v₁) = f(v₂) = 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}.