Roman domination in oriented trees

被引:2
作者
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
    Chambers, Erin W.
    Kinnersley, Bill
    Prince, Noah
    West, Douglas B.
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) : 1575 - 1586
  • [2] Roman domination in graphs
    Cockayne, EJ
    Dreyer, PA
    Hedetniemi, SM
    Hedetniemi, ST
    [J]. DISCRETE MATHEMATICS, 2004, 278 (1-3) : 11 - 22
  • [3] A NOTE ON ROMAN DOMINATION OF DIGRAPHS
    Hao, Guoliang
    Xie, Zhihong
    Chen, Xiaodan
    [J]. 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
    Ouldrabah, Lyes
    Blidia, Mostafa
    Bouchou, Ahmed
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) : 667 - 679
  • [8] Total Roman domination for proper interval graphs
    Poureidi, Abolfazl
    [J]. 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., 2011, Acta Univ. Apulensis Math. Inform., V27, P77