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

Abstract

In this paper, we show that the Italian domination number of every lexicographic product graph $G\circ 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\in V(G)$, and let $w=(w_0,w_1,\dots ,w_l)$ be a vector of nonnegative integers such that $w_0\ge 1$. We say that a function $f:V(G)⟶\{0,1,\dots ,l\}$ is a $w$-dominating function if $f(N(v))={\sum }_{u\in N(v)}f(u)\ge w_i$ for every vertex $v$ with $f(v)=i$. The weight of $f$ is defined to be $\omega (f)={\sum }_{v\in V(G)}f(v)$. The $w$-domination number of $G$, denoted by ${\gamma }_w(G)$, is the minimum weight among all $w$-dominating functions on $G$. If we impose restrictions on the minimum degree of $G$ when needed, under this approach we can define, for instance, the domination number, the total domination number, the $k$-domination number, the $k$-tuple domination number, the $k$-tuple total domination number, the Italian domination number, the total Italian domination number, and the $\{k\}$-domination number. Specifically, we show that ${\gamma }_I(G\circ H)={\gamma }_w(G)$, where $w\in \{2\}\times \{0,1,2{\}}^l$ and $l\in \{2,3\}$. The decision on whether the equality holds for specific values of $w_0,\dots ,w_l$ will depend on the value of the domination number of $H$. This paper also provides preliminary results on ${\gamma }_w(G)$ and raises the challenge of conducting a detailed study of the topic.

References in corpus (1)

• Total Roman {2}-Dominating functions in Graphs

Cited by in corpus (1)

• Perfect domination, Roman domination and perfect Roman domination in lexicographic product graphs