Total Protection of Lexicographic Product Graphs

被引:7
作者
Cabrera Martinez, Abel [1 ]
Alberto Rodriguez-Velazquez, Juan [1 ]
机构
[1] Univ Rovira & Virgili, Dept Engn Informat & Matemat, Av Paisos Catalans 26, E-43007 Tarragona, Spain
关键词
total weak Roman domination; secure total domination; total domination; lexicographic product; ITALIAN DOMINATION; ROMAN;
D O I
10.7151/dmgt.2318
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a graph G with vertex set V (G), a function f : V (G) -> {0, 1, 2} is said to be a total dominating function if sigma(u)(is an element of)(N)(()(v)()) f(u) > 0 for every v is an element of V (G), where N(v) denotes the open neighbourhood of v. Let V-i = {x is an element of V (G) : f(x) = i}. A total dominating function f is a total weak Roman dominating function if for every vertex v is an element of V-0 there exists a vertex u is an element of N(v) boolean AND (V-1 ? V-2) such that the function f ', defined by f '(v) = 1, f '(u) = f(u) - 1 and f '(x) = f(x) whenever x is an element of V (G) \ {u, v}, is a total dominating function as well. If f is a total weak Roman dominating function and V-2 = null , then we say that f is a secure total dominating function. The weight of a function f is defined to be omega(f) = sigma(v)(is an element of)(V) (()(G)()) f(v). The total weak Roman domination number (secure total domination number) of a graph G is the minimum weight among all total weak Roman dominating functions (secure total dominating functions) on G. In this article, we show that these two parameters coincide for lexicographic product graphs. Furthermore, we obtain closed formulae and tight bounds for these parameters in terms of invariants of the factor graphs involved in the product.
引用
收藏
页码:967 / 984
页数:18
相关论文
共 22 条
[11]  
Cockayne EJ, 2005, UTILITAS MATHEMATICA, V67, P19
[12]   TOTAL DOMINATION IN GRAPHS [J].
COCKAYNE, EJ ;
DAWES, RM ;
HEDETNIEMI, ST .
NETWORKS, 1980, 10 (03) :211-219
[13]   Roman domination in graphs [J].
Cockayne, EJ ;
Dreyer, PA ;
Hedetniemi, SM ;
Hedetniemi, ST .
DISCRETE MATHEMATICS, 2004, 278 (1-3) :11-22
[14]   Secure total domination in graphs: Bounds and complexity [J].
Duginov, Oleg .
DISCRETE APPLIED MATHEMATICS, 2017, 222 :97-108
[15]   Perfect Italian domination in trees [J].
Haynes, Teresa W. ;
Henning, Michael A. .
DISCRETE APPLIED MATHEMATICS, 2019, 260 :164-177
[16]   Defending the Roman Empire - A new strategy [J].
Henning, MA ;
Hedetniemi, ST .
DISCRETE MATHEMATICS, 2003, 266 (1-3) :239-251
[17]  
Henning MA., 2013, Total domination in graphs, DOI [10.1007/978-1-4614-6525-6, DOI 10.1007/978-1-4614-6525-6]
[18]   Italian domination in trees [J].
Henning, Michael A. ;
Klostermeyer, William F. .
DISCRETE APPLIED MATHEMATICS, 2017, 217 :557-564
[19]  
Klostermeyer William F., 2008, Discussiones Mathematicae Graph Theory, V28, P267
[20]   RELATIONS BETWEEN PACKING AND COVERING NUMBERS OF A TREE [J].
MEIR, A ;
MOON, JW .
PACIFIC JOURNAL OF MATHEMATICS, 1975, 61 (01) :225-233