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\notin E(G)$. In this paper, we characterize all ${\gamma }_R$-edge critical connected graphs having precisely two cycles.