Critical graphs with Roman domination number four. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Martínez-Pérez, A.; Oliveros, D.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 804
• Page End: 809
• Publication Date: 2020-09-01
• Subjects: Roman domination -- critical; 05C69
• DOI: 10.1016/j.akcej.2019.12.015
• Languages: English
• ISSNs: 0972-8600

Abstract

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 .