2013/11/18 by Martínez-Pérez, A., Oliveros, D.
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1311.4476
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 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" has been defined in general as the study of graphs where the Roman domination number decreases when removing an edge or a vertex of the graph. In this paper we give further results in this topic as well as the complete characterization of critical graphs that have Toman Domination number γR(G)=4.