Roman domination in oriented trees

被引:3
作者
Ouldrabah, Lyes [1 ]
Blidia, Mostafa [1 ]
Bouchou, Ahmed [2 ]
机构
[1] Univ Blida 1, Lamda RO Dept Math, BR 270, Blida, Algeria
[2] Univ Medea, Dept Math, Medea, Algeria
关键词
Roman domination; digraph; oriented tree; EXTREMAL PROBLEMS;
D O I
10.5614/ejgta.2021.9.1.9
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let D = (V, A) be a digraph of order n = vertical bar V vertical bar. A Roman dominating function of a digraph D is a function f : V -> {0, 1, 2} such that every vertex a for which f (u) = 0 has an in- neighbor v for which f (v) = 2. The weight of a Roman dominating function is the value f (V) = Sigma(u is an element of v) f (u). The minimum weight of a Roman dominating function of a digraph D is called the Roman domination number of D, denoted by gamma(R) (D). In this paper, we characterize oriented trees T satisfying gamma(R) (T) + Delta(+) (T) = n + 1.
引用
收藏
页码:95 / 103
页数:9
相关论文
共 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]   Roman domination in graphs [J].
Cockayne, EJ ;
Dreyer, PA ;
Hedetniemi, SM ;
Hedetniemi, ST .
DISCRETE MATHEMATICS, 2004, 278 (1-3) :11-22
[3]   A NOTE ON ROMAN DOMINATION OF DIGRAPHS [J].
Hao, Guoliang ;
Xie, Zhihong ;
Chen, Xiaodan .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) :13-21
[4]  
Haynes T.W., 2020, TOPICS DOMINATION GR
[5]  
Kamaraj M., 2011, INT J COMB GRAPH THE, V4, P103
[6]  
Kamaraj M., ROMAN DOMINATI UNPUB
[7]   Extremal digraphs for an upper bound on the Roman domination number [J].
Ouldrabah, Lyes ;
Blidia, Mostafa ;
Bouchou, Ahmed .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) :667-679
[8]   Total Roman domination for proper interval graphs [J].
Poureidi, Abolfazl .
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2020, 8 (02) :401-413
[9]  
Rad NJ, 2017, ELECTRON J GRAPH THE, V5, P1, DOI 10.5614/ejgta.2017.5.1.1
[10]  
Sheikholeslami S. M., 2011, Acta Univ. Apulensis Math. Inform., V27, P77