Perfect Italian domination in trees

被引:28
作者
Haynes, Teresa W. [1 ,2 ]
Henning, Michael A. [2 ]
机构
[1] East Tennessee State Univ, Dept Math & Stat, Johnson City, TN 37614 USA
[2] Univ Johannesburg, Dept Pure & Appl Math, ZA-2006 Auckland Pk, South Africa
基金
新加坡国家研究基金会;
关键词
Italian domination; Roman domination; Roman {2)-domination; ROMAN DOMINATION;
D O I
10.1016/j.dam.2019.01.038
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A perfect Italian dominating function on a graph G is a function f : V(G) -> {0, 1, 2} satisfying the condition that for every vertex u with f (u) = 0, the total weight off assigned to the neighbors of u is exactly two. The weight of a perfect Italian dominating function is the sum of the weights of the vertices. The perfect Italian domination number of G, denoted gamma(p)(I)(G), is the minimum weight of a perfect Italian dominating function of G. We show that if G is a tree on n >= 3 vertices, then gamma(p)(I)(G) <= 4/5n, and for each positive integer n (math) 0 (mod 5) there exists a tree of order n for which equality holds in the bound. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码:164 / 177
页数:14
相关论文
共 21 条
[1]   Double Roman domination [J].
Beeler, Robert A. ;
Haynes, Teresa W. ;
Hedetniemi, Stephen T. .
DISCRETE APPLIED MATHEMATICS, 2016, 211 :23-29
[2]   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
[3]   Roman {2}-domination [J].
Chellali, Mustapha ;
Haynes, Teresa W. ;
Hedetniemi, Stephen T. ;
McRae, Alice A. .
DISCRETE APPLIED MATHEMATICS, 2016, 204 :22-28
[4]   Roman domination in graphs [J].
Cockayne, EJ ;
Dreyer, PA ;
Hedetniemi, SM ;
Hedetniemi, ST .
DISCRETE MATHEMATICS, 2004, 278 (1-3) :11-22
[5]   ROMAN DOMINATION IN CARTESIAN PRODUCT GRAPHS AND STRONG PRODUCT GRAPHS [J].
Gonzalez Yero, Ismael ;
Alberto Rodriguez-Velazquez, Juan .
APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2013, 7 (02) :262-274
[6]  
Haynes T. W., 1998, FUNDAMENTALS DOMINAT, V1st, DOI [10.1201/9781482246582, DOI 10.1201/9781482246582]
[7]  
Henning M., 2002, DISCUSS MATH GRAPH T, V22, P325
[8]  
Henning M. A., 2013, Total Domination in Graphs
[9]   Perfect Roman domination in trees [J].
Henning, Michael A. ;
Klostermeyer, William F. ;
MacGillivray, Gary .
DISCRETE APPLIED MATHEMATICS, 2018, 236 :235-245
[10]   Italian domination in trees [J].
Henning, Michael A. ;
Klostermeyer, William F. .
DISCRETE APPLIED MATHEMATICS, 2017, 217 :557-564