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

Abel Cabrera Martínez ; Alejandro Estrada-Moreno ; Juan Alberto Rodríguez-Velázquez

Ars Mathematica Contemporanea, Tome 22 (2022) no. 1, article no. 04, 25 p.

Résumé

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.

Détail

DOI : 10.26493/1855-3974.2318.fb9

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