Roman Domination Edge Critical Graphs Having Precisely Two Cycles

Abstract

A Roman dominating function on a graph \(G\) is a function \(f: V(G) \to \{0, 1, 2\}\) satisfying the condition that every vertex \(u\) of \(G\) for which \(f(u) = 0\) is adjacent to at least one vertex \(v\) of \(G\) for which \(f(v) = 2\). The weight of a Roman dominating function is the value \(f(V(G)) = \sum_{u \in V(G)} f(u)\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum weight of a Roman dominating function on \(G\). A graph \(G\) is said to be Roman domination edge critical, or simply \(\gamma_R\)-edge critical, if \(\gamma_R(G + e) < \gamma_R(G)\) for any edge \(e \not\in E(G)\). In this paper, we characterize all \(\gamma_R\)-edge critical connected graphs having precisely two cycles.