From (Secure) w-Domination in Graphs to Protection of Lexicographic Product Graphs

Abstract

Let w = (w0,w1, . . . ,wl) be a vector of nonnegative integers such that w0 ≥ 1. Let G be a graph and N(v) the open neighbourhood of v ∈ V(G). We say that a function f : V(G) −→{0,1, . . . , l} is a w-dominating function if f (N(v)) = åu∈N(v) f (u) ≥ wi for every vertex v with f (v) = i. The weight of f is defined to be w( f ) =åv∈V(G) f (v). Given a w-dominating function f and any pair of adjacent vertices v,u ∈ V(G) with f (v) = 0 and f (u) > 0, the function fu→v is defined by fu→v(v) = 1, fu→v(u) = f (u) −1 and fu→v(x) = f (x) for every x ∈ V(G) \ {u,v}. We say that a w-dominating function f is a secure w-dominating function if for every v with f (v) = 0, there exists u ∈ N(v) such that f (u) > 0 and fu→v is a w-dominating function as well. The (secure) w-domination number of G, denoted by (gsw (G)) gw(G), is defined as the minimum weight among all (secure) w-dominating functions. In this paper, we show how the secure (total) domination number and the (total) weak Roman domination number of lexicographic product graphs G◦H are related to gsw (G) or gw(G). For the case of the secure domination number and the weak Roman domination number, the decision on whether w takes specific components will depend on the value of g s (1,0)(H), while in the case of the total version of these parameters, the decision will depend on the value of g s (1,1)(H).