From Italian domination in lexicographic product graphs to w-domination in graphs




Italian domination, w-domination, k-domination, k-tuple domination, lexicographic product graph


In this paper, we show that the Italian domination number of every lexicographic product graph G ○ H can be expressed in terms of five different domination parameters of G. These parameters can be defined under the following unified approach, which encompasses the definition of several well-known domination parameters and introduces new ones.

Let N(v) denote the open neighbourhood of v ∈ V(G), and let w = (w0, w1, …, wl) be a vector of nonnegative integers such that w0 ≥ 1. 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 ω(f) = ∑v ∈ V(G)f(v). The w-domination number of G, denoted by γw(G), is the minimum weight among all w-dominating functions on G.

Specifically, we show that γI(G ○ H) = γw(G), where w ∈ {2} × {0, 1, 2}l and l ∈ {2, 3}. The decision on whether the equality holds for specific values of w0, …, wl will depend on the value of the domination number of H. This paper also provides preliminary results on γw(G) and raises the challenge of conducting a detailed study of the topic.

Author Biography

Juan Alberto Rodríguez-Velázquez, Universitat Rovira i Virgili, Spain