Critical graphs with Roman domination number four

被引:0
作者
Martinez-Perez, A. [1 ]
Oliveros, D. [2 ]
机构
[1] Fac CC Soci Talavera, Avda Real Fabrica de Seda S-N, Toledo 45600, Spain
[2] Univ Nacl Autonoma Mexico, Inst Math, Mexico City, DF, Mexico
关键词
Roman domination; critical; 05C69;
D O I
10.1016/j.akcej.2019.12.015
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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))=<mml:munder>Sigma u is an element of V(G)</mml:munder>r(u). The Roman domination number gamma 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 gamma R(G)=4.
引用
收藏
页码:804 / 809
页数:6
相关论文
共 13 条
[1]   EXTREMAL PROBLEMS FOR ROMAN DOMINATION [J].
Chambers, Erin W. ;
Kinnersley, Bill ;
Prince, Noah ;
West, Douglas B. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) :1575-1586
[2]  
Chellali M, 2012, AKCE INT J GRAPHS CO, V9, P195
[3]  
Chellali M, 2015, UTILITAS MATHEMATICA, V96, P165
[4]   Roman domination in graphs [J].
Cockayne, EJ ;
Dreyer, PA ;
Hedetniemi, SM ;
Hedetniemi, ST .
DISCRETE MATHEMATICS, 2004, 278 (1-3) :11-22
[5]   On the Roman domination number of a graph [J].
Favaron, O. ;
Karami, H. ;
Khoeilar, R. ;
Sheikholeslami, S. M. .
DISCRETE MATHEMATICS, 2009, 309 (10) :3447-3451
[6]   ON THE ROMAN DOMINATION STABLE GRAPHS [J].
Hajian, Majid ;
Rad, Nader Jafari .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (04) :859-871
[7]  
Haynes T. W, 2013, Fundamentals of Domination in Graphs
[8]  
Rad NJ, 2017, ARS COMBINATORIA, V131, P355
[9]  
Rad NJ, 2013, UTILITAS MATHEMATICA, V92, P73
[10]  
Rad NJ, 2012, UTILITAS MATHEMATICA, V89, P79