JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2022, Vol. 57 ›› Issue (11): 21-25.doi: 10.6040/j.issn.1671-9352.0.2021.003

Previous Articles    

Bounds on the double Roman domination number of graphs

XIE Zhi-hong, HAO Guo-liang*   

  1. College of Science, East China University of Technology, Nanchang 330013, Jiangxi, China
  • Published:2022-11-10

PDF (PC)

276

Abstract: A function f:V(G)→{0,1,2,3}defined on the vertex set V(G)of a graph G is called a double Roman dominating function if any vertex assigned 0 is adjacent to at least one vertex assigned 3 or two vertices assigned 2, and any vertex assigned 1 is adjacent to at least one vertex assigned 2 or 3. The weight of a double Roman dominating function is the sum of assigned values of all vertices. The double Roman domination number of a graph G is defined as the minimum weight of a double Roman dominating function on G. Using the number of vertices, girth, circumference and minimum degree of graphs, some lower and upper bounds on the double Roman domination number of graphs with a cycle are established.

Key words: double Roman dominating function, double Roman domination number, girth, circumference

CLC Number: 

  • O157.5
[1] YUE Jun, SONG Jiamei. Note on the perfect Roman domination number of graphs[J]. Applied Mathematics and Computation, 2020, 364(1):124685.
[2] MA Yuede, CAI Qingqing, YAO Shunyu. Integer linear programming models for the weighted total domination problem[J].Applied Mathematics and Computation, 2019, 358:146-150.
[3] WU Pu, JIANG Huiqin, NAZARI-MOGHADDAM S, et al. Independent domination stable trees and unicyclic graphs[J].Mathematics, 2019, 7:820.
[4] HAYNES T W, HENNING M A, VOLKMANN L. Graphs with large Italian domination number[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43(6):4273-4287.
[5] GHAREGHANI N, PETERIN I, SHARIFANI P. A note on bipartite graphs whose[1,k] -domination number equal to their number of vertices[J]. Opuscula Mathematica, 2020, 40:375-382.
[6] 朱晓颖,逄世友.控制数给定的树的最大离心距离和[J]. 山东大学学报(理学版), 2017, 52(2):30-36. ZHU Xiaoying, PANG Shiyou. On the maximal eccentric distance sum of tree with given domination number[J]. Journal of Shandong University(Natural Science), 2017, 52(2):30-36.
[7] AMJADI J, NAZARI-MOGHADDAM S, SHEIKHOLESLAMI S M, et al. An upper bound on the double Roman domination number[J]. Journal of Combinatorial Optimization, 2018, 36:81-89.
[8] ZHANG X, LI Z, JIANG H, et al. Double Roman domination in trees[J]. Information Processing Letters, 2018, 134:31-34.
[9] HENNING M A, JAFARI RAD N. A characterization of double Roman trees[J]. Discrete Applied Mathematics, 2019, 259:100-111.
[10] BEELER R A, HAYNES T W, HEDETNIEMI S T. Double Roman domination[J]. Discrete Applied Mathematics, 2016, 211:23-29.
[11] SHAO Zehui, SHEIKHOLESLAMI S M, NAZARI-MOGHADDAM S, et al. Global double Roman domination in graphs[J]. Journal of Discrete Mathematical Sciences and Cryptography, 2019, 22:31-44.
[12] ABDOLLAHZADEH AHANGAR H, CHELLALI M, SHEIKHOLESLAMI S M. On the double Roman domination in graphs[J]. Discrete Applied Mathematics, 2017, 232:1-7.
[1] SUN Shuang, LIU Hong-xing. The inclusion graph of S-acts [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(8): 121-126.
[2] ZHU Hai-yang, GU Yu, LÜ Xin-zhong. New upper bound on the chromatic number of the square of a planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(2): 94-101.
[3] MA Gang. Acyclic list edge coloring of planar graphs with girth #br# ≥ 11 and maximum degree 3 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(2): 18-23.
[4] DING Wei. Acyclic edge coloring of planar graphs without 4-Cycles [J]. J4, 2012, 47(6): 76-79.
[5] ZHU Hai-yang1, HOU Li-feng1, CHEN Wei1, Lü Xin-zhong2. The L(p,q)-labeling of planar graphs with girth g(G)≥5 [J]. J4, 2011, 46(8): 95-103.
[6] ZHU Hai-yang1, L Xin-zhong2, SHENG Jing-jun1, HANG Dan3 . The L(p,q)-labeling of planar graphs with girth g(G)≥6 [J]. J4, 2011, 46(4): 9-16.
[7] LI Shuo,LI Feng,LIANG Feng . The heterochromatic girth in edge-colored graphs [J]. J4, 2008, 43(6): 19-20 .
[8] ZHU Xiao-ying,XU Yang,SHI Hong-jun . The 3-choosability of plane graphs without3-， 6-,9- and 10-cycles [J]. J4, 2007, 42(10): 59-62 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd