From w-Domination in Graphs to Domination Parameters in Lexicographic Product Graphs

Identifier:  imarina:9296663

Handle: https://hdl.handle.net/20.500.11797/imarina9296663

Authors:  Cabrera-Martínez, A; Montejano, LP; Rodríguez-Velázquez, JA

Abstract:
A wide range of parameters of domination in graphs can be defined and studied through a common approach that was recently introduced in [https://doi.org/10.26493/1855-3974.2318.fb9] under the name of w-domination, where w= (w, w1, ⋯ , wl) is a vector of non-negative integers such that w≥ 1. Given a graph G, a function f: V(G) ⟶ { 0 , 1 , ⋯ , l} is said to be a w-dominating function if ∑ u∈N(v)f(u) ≥ wi for every vertex v with f(v) = i, where N(v) denotes the open neighbourhood of v∈ V(G). The weight of f is defined to be ω(f) = ∑ v∈V(G)f(v) , while the w-domination number of G, denoted by γw(G) , is defined as the minimum weight among all w-dominating functions on G. A wide range of well-known domination parameters can be defined and studied through this approach. For instance, among others, the vector w= (1 , 0) corresponds to the case of standard domination, w= (2 , 1) corresponds to double domination, w= (2 , 0 , 0) corresponds to Italian domination, w= (2 , 0 , 1) corresponds to quasi-total Italian domination, w= (2 , 1 , 1) corresponds to total Italian domination, w= (2 , 2 , 2) corresponds to total { 2 } -domination, while w= (k, k- 1 , ⋯ , 1 , 0) corresponds to { k} -domination. In this paper, we show that several domination parameters of lexicographic product graphs G∘ H are equal to γw(G) for some vector w∈ { 2 } × { 0 , 1 , 2 } l and l∈ { 2 , 3 }. The decision on whether the equality holds for a specific vector w will depend on the value of some domination parameters of H. In particular, we focus on quasi-total Italian domination, total Italian domination, 2-domination, double domination, total { 2 } -domination, and double total domination of lexicographic product graphs.