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

Abel Cabrera Martinez, Alejandro Estrada-Moreno, Juan Alberto Rodriguez-Velazquez


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.


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

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications