On the Double Roman Domination in Generalized Petersen Graphs P(5k,k)

被引：4
作者：
Rupnik Poklukar, Darja [1 ]
Zerovnik, Janez [1 ,2 ]
机构：
[1] Univ Ljubljana, Fac Mech Engn, Askerceva 6, Ljubljana 1000, Slovenia
[2] Inst Math Phys & Mech, Jadranska 19, Ljubljana 1000, Slovenia
来源：
MATHEMATICS | 2022年 / 10卷 / 01期
关键词：
double Roman domination; generalized Petersen graph; discharging method; graph cover; double Roman graph; NUMBER; P(N; BOUNDS; P(CK;
D O I：
10.3390/math10010119
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A double Roman dominating function on a graph G=(V,E) is a function f:V & RARR;{0,1,2,3} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and every vertex u with f(u)=1 is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w(f)= n-ary sumation( v & ISIN;V)f(v). The double Roman domination number gamma dR(G) of a graph G equals the minimum weight of a double Roman dominating function of G. We obtain closed expressions for the double Roman domination number of generalized Petersen graphs P(5k,k). It is proven that gamma(dR)(P(5k,k))=8k for k & EQUIV;2,3mod5 and 8k & LE;gamma(dR)(P(5k,k))& LE;8k+2 for k & EQUIV;0,1,4mod5. We also improve the upper bounds for generalized Petersen graphs P(20k,k).
引用
收藏
页数：19
相关论文
共 41 条
  • [1] On the double Roman domination in graphs
    Ahangar, Hossein Abdollahzadeh
    Chellali, Mustapha
    Sheikholeslami, Seyed Mahmoud
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 232 : 1 - 7
  • [2] An upper bound on the double Roman domination number
    Amjadi, J.
    Nazari-Moghaddam, S.
    Sheikholeslami, S. M.
    Volkmann, L.
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 81 - 89
  • [3] Arquilla J., 1995, Military Operations Research, V1, P3
  • [4] Algorithmic results on double Roman domination in graphs
    Banerjee, S.
    Henning, Michael A.
    Pradhan, D.
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 39 (01) : 90 - 114
  • [5] Double Roman domination
    Beeler, Robert A.
    Haynes, Teresa W.
    Hedetniemi, Stephen T.
    [J]. DISCRETE APPLIED MATHEMATICS, 2016, 211 : 23 - 29
  • [6] On the domination number of the generalized Petersen graphs
    Behzad, Arash
    Behzad, Mehdi
    Praeger, Cheryl E.
    [J]. DISCRETE MATHEMATICS, 2008, 308 (04) : 603 - 610
  • [7] Roman domination in graphs
    Cockayne, EJ
    Dreyer, PA
    Hedetniemi, SM
    Hedetniemi, ST
    [J]. DISCRETE MATHEMATICS, 2004, 278 (1-3) : 11 - 22
  • [8] Vertex domination of generalized Petersen graphs
    Ebrahimi, B. Javad
    Jahanbakht, Nafiseh
    Mahmoodian, E. S.
    [J]. DISCRETE MATHEMATICS, 2009, 309 (13) : 4355 - 4361
  • [9] On the domination number of generalized Petersen graphs P(n, 2)
    Fu Xueliang
    Yang Yuansheng
    Jiang Baoqi
    [J]. DISCRETE MATHEMATICS, 2009, 309 (08) : 2445 - 2451
  • [10] Independent Rainbow Domination Numbers of Generalized Petersen Graphs P(n, 2) and P(n, 3)
    Gabrovsek, Bostjan
    Peperko, Aljosa
    Zerovnik, Janez
    [J]. MATHEMATICS, 2020, 8 (06)
12345