Changing and unchanging the Roman domination number of a graph

被引:1
作者
Rad, Nader Jafari [1 ]
Volkmann, Lutz [2 ]
机构
[1] Shahrood Univ Technol, Dept Math, Shahrood, Iran
[2] Rhein Westfal TH Aachen, Lehrstuhl Math, D-52056 Aachen, Germany
关键词
Domination; Roman domination; Critical;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A Roman dominating function on a graph G with vertex set V (G) is a function f : V (G) -> {0,1,2} satisfying the condition that every vertex u with f(u) = 0 is adjacent to at least one vertex v with f(v) = 2. The weight of a Roman dominating function is the value f (V(G)) = Sigma(u is an element of v(G)) f(u). The Roman domination number gamma(G) of G is the minimum weight of a Roman dominating function on C. In this paper, we study how the Roman domination number changes by means of removing a vertex or an edge from a graph.
引用
收藏
页码:79 / 95
页数:17
相关论文
共 13 条
  • [1] [Anonymous], 2001, Introduction to Graph Theory
  • [2] Berge C., 1962, THEORY GRAPHS ITS AP
  • [3] VERTEX DOMINATION CRITICAL GRAPHS
    BRIGHAM, RC
    CHINN, PZ
    DUTTON, RD
    [J]. NETWORKS, 1988, 18 (03) : 173 - 179
  • [4] Roman domination in graphs
    Cockayne, EJ
    Dreyer, PA
    Hedetniemi, SM
    Hedetniemi, ST
    [J]. DISCRETE MATHEMATICS, 2004, 278 (1-3) : 11 - 22
  • [5] THE DIAMETER OF DOMINATION K-CRITICAL GRAPHS
    FAVARON, O
    SUMNER, DP
    WOJCICKA, E
    [J]. JOURNAL OF GRAPH THEORY, 1994, 18 (07) : 723 - 734
  • [6] VERTEX DOMINATION-CRITICAL GRAPHS
    FULMAN, J
    HANSON, D
    MACGILLIVRAY, G
    [J]. NETWORKS, 1995, 25 (02) : 41 - 43
  • [7] Hansberg A., UTILITAS MA IN PRESS
  • [8] Hansberg A., VERTEX EDGE CR UNPUB
  • [9] Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]
  • [10] Defendens imperium romanum: A classical problem in military strategy
    ReVelle, CS
    Rosing, KE
    [J]. AMERICAN MATHEMATICAL MONTHLY, 2000, 107 (07) : 585 - 594