Roman domination: changing, unchanging, ${\gamma }_R$-graphs

Abstract

A Roman dominating function (RD-function) on a graph $G=(V(G),E(G))$ is a labeling $f:V(G)\to \{0,1,2\}$ such that every vertex with label $0$ has a neighbor with label $2$. The weight $f(V(G))$ of a RD-function $f$ on $G$ is the value ${\Sigma }_{v\in V(G)}f(v)$. The {\em Roman domination number} ${\gamma }_R(G)$ of $G$ is the minimum weight of a RD-function on $G$. The six classes of graphs resulting from the changing or unchanging of the Roman domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. We consider relationships among the classes, which are illustrated in a Venn diagram. A graph $G$ is Roman domination $k$-critical if the removal of any set of $k$ vertices decreases the Roman domination number. Some initial properties of these graphs are studied. The ${\gamma }_R$-graph of a graph $G$ is any graph which vertex set is the collection ${\mathcal{D}}_R(G)$ of all minimum weight RD-functions on $G$. We define adjacency between any two elements of ${\mathcal{D}}_R(G)$ in several ways, and initiate the study of the obtained ${\gamma }_R$-graphs.

19 pages, 3 figures