Critical graphs with Roman domination number four
Álvaro Martínez-Pérez, Déborah Oliveros · AKCE International Journal of Graphs and Combinatorics · 2020
A Roman domination function on a graph G is a function r:V(G)→{0,1,2} satisfying the condition that every vertex u for which r(u) = 0 is adjacent to at least one vertex v for which r(v) = 2. The weight of a Roman domination function is the value r(V(G))=∑u∈V(G)r(u). The Roman domination number γR(G) of G is the minimum weight of a Roman domination function on G. “Roman Criticality” often refers to the study of graphs where the Roman domination number decreases when adding an edge or removing a vertex of the graph. In this paper we add some condition to this notion of criticality and give a complete characterization of critical graphs with Roman Domination number γR(G)=4.