A Generalization of Roman Domination Critical Graphs

Abstract

A Roman dominating function on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ satisfying the condition that every vertex $u\in V$ for which $f(u)=0$ is adjacent to a vertex $v$ for which $f(v)=2$. The weight of a Roman dominating function is the value $f(V)=\sum _{u\in V}f(u)$. The Roman domination number, ${\gamma }_R(G)$, of $G$ is the minimum weight of a Roman dominating function on $G$. In this paper, we study those graphs for which the removal of any pair of vertices decreases the Roman domination number. A graph $G$ is said to be \emph{Roman domination bicritical} or just ${\gamma }_R$-bicritical, if ${\gamma }_R(G–\{v,u\})<{\gamma }_R(G)$ for any pair of vertices $v,u\in V$. We study properties of ${\gamma }_R$-bicritical graphs, and we characterize ${\gamma }_R$-bicritical trees and unicyclic graphs.