Total Protection of Lexicographic Product Graphs

Discussiones Mathematicae Graph Theory

Martínez Abel Cabrera¹  Rodríguez-Velázquez Juan Alberto¹ 

[1] Universitat Rovira i Virgili, Departament d’Enginyeria Informàtica i Matemàtiques, Av. Països Catalans 26, 43007 Tarragona, Spain;

关键词: total weak roman domination;    secure total domination;    total domination;    lexicographic product;    05c69;    05c76;   

DOI  :  10.7151/dmgt.2318

来源: DOAJ

【 摘 要 】

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 Σu∈N(v) f(u) > 0 for every v ∈ V (G), where N(v) denotes the open neighbourhood of v. Let Vi = {x ∈ V (G) : f(x) = i}. A total dominating function f is a total weak Roman dominating function if for every vertex v ∈ V0 there exists a vertex u ∈ N(v) ∩ (V1 ∪ V2) such that the function f′, defined by f′(v) = 1, f′(u) = f(u) − 1 and f′(x) = f(x) whenever x ∈ V (G) \ {u, v}, is a total dominating function as well. If f is a total weak Roman dominating function and V2 = ∅, then we say that f is a secure total dominating function. The weight of a function f is defined to be ω(f) = Σv∈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.

【 授权许可】

Unknown