Critical graphs with Roman domination number four. Issue 3 (1st September 2020) - Martínez-Pérez, A.; Oliveros, D.
Abstract: 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 .