On the $\{2\}$-domination number of graphs

1.   Introduction

We begin by stating the main basic terminology which shall be used in the whole work. We only consider simple graphs $G$ with vertex set $V(G)$ and edge set $E(G)$. Given a vertex $v\in V(G)$, $N(v) = \{x\in V(G): xv\in E(G)\}$ and $N[v] = N(v)\cup \{v\}$. Analogously, given a set $D\subseteq V(G)$, $N(D) = \cup_{v\in D} N(v)$ and $N[D] = N(D)\cup D$. The graph obtained from $G$ by removing all the vertices in $D\subseteq V(G)$ and all the edges incident with a vertex in $D$ will be denoted by $G-D$. A vertex $v\in V(G)$ is a leaf of $G$ if $|N(v)| = 1$, and $v$ is a support vertex of $G$ if it is adjacent to a leaf. The set of leaves and support vertices are denoted by $\mathcal{L}(G)$ and $\mathcal{S}(G)$, respectively. In addition, $v\in V(G)$ is a semi-support vertex if $v\in N(\mathcal{S}(G))\setminus (\mathcal{S}(G)\cup \mathcal{L}(G))$. The set of semi-support vertices is denoted by $\mathcal{SS}(G)$. Moreover, by attaching a path $P$ to a vertex $v$ of $G$ we mean adding the path $P$ and joining $v$ to a leaf of $P$. Given two vertices $u$ and $v$ of $G$, the distance between $u$ and $v$, denoted by $d(u, v)$, is the minimum length of a $u-v$ path. The diameter of $G$, denoted by $\operatorname{diam}(G)$, is the maximum distance among pairs of vertices of $G$. A diametral path in $G$ is a shortest path whose length equals the diameter of the graph. Let $k\geq 1$ be an integer and $f: V(G)\rightarrow \{0, \ldots, k\}$ be a function on $G$. Given a set $X\subseteq V(G)$, $f(X) = \sum_{x\in X}f(x)$. For every $i\in \{0, \ldots, k\}$, let $V_i = \{v\in V(G):\; f(v) = i\}$. We use the notation $f(V_0, \ldots, V_k)$ for identifying the function $f$ and the subsets $V_0, \ldots, V_k$ associated with it.

A set $D\subseteq V(G)$ is a dominating set of $G$ if $N(v)\cap D\neq \emptyset$ for every $v\in V(G)\setminus D$. The domination number of $G$, denoted by $\gamma(G)$, is the minimum cardinality among all dominating sets of $G$. The dominating sets and its variants in graphs are interesting study topics in graph theory. We refer to the books ^[1,2,3] for theoretical results and practical applications.

Recently, Cabrera-Martínez et al. ^[4] introduced the following approach to the theory of domination in graphs. Given a vector of nonnegative integers $w = (w_0, \ldots, w_k)$ (with $w_0\ge 1$), a function $f(V_0, \ldots, V_k)$ is a $w$-dominating function on $G$ if $f(N(v))\geq w_i$ for every $v\in V_i$. The minimum weight $\omega(f) = f(V(G)) = \sum_{i = 1}^k i|V_i|$ among all $w$-dominating functions on $G$ is the $w$-domination number of $G$, and is denoted by $\gamma_{w}(G)$. A $w$-dominating function with weight $\gamma_{w}(G)$ will be called a $\gamma_{w}(G)$-function. This approach covers some different versions of domination known so far. The next particular cases of well-known domination parameters we can defined in terms of $w$-domination as follows.

● The domination number of a graph $G$ is defined to be $\gamma(G) = \gamma_{(1, 0)}(G)$. Given a $(1, 0)$-dominating function $f(V_0, V_1)$ on $G$, we say that $V_1$ is a dominating set of $G$. If $f$ is a $\gamma_{(1, 0)}(G)$-function, then $V_1$ will be called a $\gamma(G)$-set.

● The total domination number of a graph $G$ with no isolated vertex is defined to be $\gamma_t(G) = \gamma_{(1, 1)}(G)$. In this case, if $f(V_0, V_1)$ is a $(1, 1)$-dominating function on $G$, then we say that $V_1$ is a total dominating set of $G$. In addition, if $f$ is a $\gamma_{(1, 1)}(G)$-function, then $V_1$ is a $\gamma_t(G)$-set. Detailed information on total domination in graphs can be found in the excellent book ^[5] and the survey ^[6].

● The double domination number of a graph $G$ with no isolated vertex is defined to be $\gamma_{\times 2}(G) = \gamma_{(2, 1)}(G)$. In this case, if $f(V_0, V_1)$ is a $\gamma_{(2, 1)}(G)$-function, then $V_1$ is a $\gamma_{\times 2}(G)$-set. The concept of double domination in graphs are widely studied, see for example ^[7,8,9,10].

● The Italian domination number of $G$ is defined to be $\gamma_{I}(G) = \gamma_{(2, 0, 0)}(G)$. This parameter was introduced by Chellali et al. in ^[11] under the name of Roman $\{2\}$-domination number and studied further in ^[12,13].

● The total Italian domination number of a graph $G$ with no isolated vertex is defined to be $\gamma_{tI}(G) = \gamma_{(2, 1, 1)}(G)$. This parameter was introduced by Cabrera García et al. in ^[14], and independently by Abdollahzadeh Ahangar et al. in ^[15], under the name of total Roman $\{2\}$-domination number. This concept was studied further in ^[16] for the lexicographic product graphs.

● The $\{2\}$-domination number of a graph $G$ is defined as $\gamma_{\{2\}}(G) = \gamma_{(2, 1, 0)}(G)$. This parameter was studied in ^{[17,18,19,20]}.

In this paper we continue with the study of the last one of the aforementioned parameters: the $\{2\}$-domination number of a graph. In Section 2, we give new combinatorial results which show the close relationship that exists between the $\{2\}$-domination number and other domination parameters of graphs. In Section 3 we analyse the case of trees. In particular, we show that the $\{2\}$-domination number of any tree is exactly twice the domination number. Finally, Section 4 shows how the $\{2\}$-domination number of lexicographic product graphs $G\circ H$ is related to $\gamma_w(G)$. In particular, the decision on whether $w$ takes specific components will depend on the value of $\gamma(H)$.

2.   Combinatorial results

To begin this section, we show some known relationships between the $\{2\}$-domination number and other previously defined known domination parameters.

Theorem 2.1. The following inequality chains hold for any graph $G$ with no isolated vertex.

${\rm (i)}$ $\gamma(G)+1\leq \gamma_{\{2\}}(G)\leq 2\gamma(G).$ ^[7]

${\rm (ii)}$ $\gamma_I(G)\leq \gamma_{\{2\}}(G)\leq \gamma_{\times 2}(G)-|\mathcal{L}(G)|+|\mathcal{S}(G)|.$ ^[4]

The next results provide equivalent conditions for the graphs $G$ with no isolated vertex that satisfy the equalities given in Theorem 2.1-(i), i.e., $\gamma_{\{2\}}(G) = 2\gamma(G)$ and $\gamma_{\{2\}}(G) = \gamma(G)+1$.

Proposition 2.2. For any graph $G$ with no isolated vertex, the following statements are equivalent.

${\rm (a)}$ $\gamma_{\{2\}}(G) = 2\gamma(G)$.

${\rm (b)}$ There exists a $\gamma_{\{2\}}(G)$-function $f(V_0, V_1, V_2)$ such that $V_1 = \emptyset$.

Proof. First, we assume that $\gamma_{\{2\}}(G) = 2\gamma(G)$. Hence, for any $\gamma(G)$-set $D$, the function $g(W_0, W_1, W_2)$, defined by $W_0 = V(G)\setminus D$, $W_1 = \emptyset$ and $W_2 = D$, is a $\{2\}$-dominating function on $G$ with $\omega(g) = 2|W_2| = 2|D| = 2\gamma(G) = \gamma_{\{2\}}(G)$. This implies that $g$ is a $\gamma_{\{2\}}(G)$-function such that $W_1 = \emptyset$. Therefore, (b) follows.

Conversely, if there exists a $\gamma_{\{2\}}(G)$-function $f(V_0, V_1, V_2)$ such that $V_1 = \emptyset$, then $V_2$ is a dominating set of $G$. Hence, $2\gamma(G)\leq 2|V_2| = \omega(f) = \gamma_{\{2\}}(G)$. Thus, it follows from Theorem 2.1-(i) that $\gamma_{\{2\}}(G) = 2\gamma(G)$, which completes the proof.

Theorem 2.3. For any graph $G$ with no isolated vertex, the following statements are equivalent.

${\rm (a)}$ $\gamma_{\{2\}}(G) = \gamma(G)+1$.

${\rm (b)}$ $\gamma(G) = 1$ or $\gamma_{\times 2}(G) = \gamma(G)+1$.

Proof. First, we assume that $\gamma_{\{2\}}(G) = \gamma(G)+1$. Let $f(V_0, V_1, V_2)$ be a $\gamma_{\{2\}}(G)$-function. The fact that $V_1\cup V_2$ is a dominating set of $G$ implies that

Hence, $|V_2|\leq 1$. If $V_2 = \emptyset$, then $V_1$ is a double dominating set of $G$. Hence, $\gamma_{\times 2}(G)\leq |V_1| = \gamma_{\{2\}}(G) = \gamma(G)+1$ and, since $|\mathcal{L}(G)|\geq |\mathcal{S}(G)|$, we deduce that $\gamma_{\times 2}(G) = \gamma(G)+1$ by Theorem 2.1. So, assume that $V_2 = \{v\}$. Suppose now that there exists a vertex $u\in V_1$. Notice that the set $(V_1\cup \{v\})\setminus \{u\}$ is a dominating set of $G$. Hence, $\gamma(G)+1\leq |(V_1\cup \{v\})\setminus \{u\}|+1 = |V_1|+1 = \gamma_{\{2\}}(G)-1$, a contradiction. Therefore, we must have $V_1 = \emptyset$, which implies that $N(v) = V(G)$, i.e., $\gamma(G) = 1$.

Conversely, if $\gamma(G) = 1$ or $\gamma_{\times 2}(G) = \gamma(G)+1$, then it follows from Theorem 2.1 that $\gamma_{\{2\}}(G) = \gamma(G)+1$, which completes the proof.

In ^[7], the authors showed that the bound $\gamma_{\{2\}}(G)\geq \gamma(G)+1$ is tight. On the other hand, the following theorem shows that this bound has room for improvement.

Theorem 2.4. For any connected graph $G$,

Proof. Let $f(V_0, V_1, V_2)$ be a $\gamma_{\{2\}}(G)$-function. Let $P = v_0v_1\cdots v_k$ be a diametrical path of $G$ ($k = \operatorname{diam}(G)$) and let $D = \{v_0, v_5, \ldots, v_{5\lfloor k/5\rfloor}\}$. Hence, $d(x, y)\geq 5$ for any different vertices $x, y\in D$. Recall that $f(N[x])\geq 2$ for every vertex $x\in V(G)$. Let $V_1'\subseteq V_1\cap N[D]$ be a set of maximum cardinality such that $|N[x]\cap V_1'|\leq 1$ for every $x\in D$. Hence, by the definitions of $D$ and $V_1'$, we have that $d(x, y)\geq 3$ for any different vertices $x, y\in V_1'$. Now, we claim that $S = (V_1\cup V_2)\setminus V_1'$ is a dominating set of $G$. Indeed, suppose to the contrary that there exists $u\in V(G)\setminus S$ such that $N(u)\cap S = \emptyset$. This implies that either $u\in V_1'$ or $u\in V_0$ and $N(u)\cap V_1'\neq \emptyset$. Since $f(N[u])\geq 2$ and $d(x, y)\geq 3$ for any different vertices $x, y\in V_1'$, we deduce that $N(u)\cap S\neq \emptyset$, a contradiction. Therefore, $S$ is a dominating set of $G$, which implies that

Hence, the proof is complete.

Let $\mathcal{G}$ be the family of graphs $G_r$ defined as follows. For every integer $r\geq 3$, the graph $G_r\in \mathcal{G}$ is obtained from two different copies of a star $T_1\cong T_2\cong K_{1, r}$ (where $h_1\in \mathcal{L}(T_1)$ and $h_2\in \mathcal{L}(T_2)$) such that $V(G_r) = V(T_1)\cup V(T_2)$ and $E(G_r) = E(T_1)\cup E(T_2)\cup \{h_1h_2\}$. Figure 1 shows the graph $G_6\in \mathcal{G}$. Observe that the equality of the bound given in Theorem 2.4 is achieved for the graphs $G_r\in \mathcal{G}$ since $\gamma_{\{2\}}(G_r) = 4$, $\gamma(G_r) = 2$ and $\operatorname{diam}(G_r) = 5$ for any integer $r\geq 3$.

The next proposition shows a simple relationship between the $\{2\}$-domination number and the Italian domination number.

Proposition 2.5. The following statements hold for any graph $G$ with no isolated vertex.

${\rm (i)}$ $\gamma_{\{2\}}(G)\leq 2\gamma_{I}(G)-1.$

${\rm (ii)}$ If $\gamma_{I}(G)\geq \gamma(G)+1$, then $\gamma_{\{2\}}(G)\leq 2\gamma_{I}(G)-2.$

Proof. First, we proceed to prove (i). Let $f(V_0, V_1, V_2)$ be a $\gamma_I(G)$-function. Now, let $D\subseteq V(G)$ be a set of minimum cardinality among all the sets satisfying that $N(x)\cap D\neq \emptyset$ for every $x\in V_1$. By the definition of $f$ and the minimality of $|D|$, it is easy to check that $|D|\leq |V_1|+|V_2|-1$. Now, notice that the function $g(W_0, W_1, W_2)$, defined by $W_1 = V_1\cup D$, $W_2 = V_2$ and $W_0 = V(G)\setminus (W_1\cup W_2)$, is a $\{2\}$-dominating function on $G$ with weight $\omega(g) = \omega(f)+|D|$. Therefore,

which completes the proof of (i). Finally, if $\gamma_{I}(G)\geq \gamma(G)+1$, then by Theorem 2.1-(i) we deduce that $\gamma_{\{2\}}(G)\leq 2\gamma(G)\leq 2\gamma_{I}(G)-2,$ which completes the proof.

By Proposition 2.5 we can deduce that the equality $\gamma_I(G) = \gamma(G)$ is a necessary condition for the graphs that satisfy the condition $\gamma_{\{2\}}(G) = 2\gamma_{I}(G)-1,$ but it is not a sufficient condition. For instance, observe that the graph $G$ given in Figure 2 satisfies $\gamma_I(G) = \gamma(G) = 4$ and $\gamma_{\{2\}}(G) = 6 < 2\gamma_{I}(G)-1.$ Therefore, we pose the following open problem.

Problem 2.6. Characterize the graphs $G$ satisfying the equality $\gamma_{\{2\}}(G) = 2\gamma_{I}(G)-1.$

The next result relates the $\{2\}$-domination number with the domination number, the total domination number and the total Italian domination number of a graph with no isolated vertex.

Theorem 2.7. For any graph $G$ with no isolated vertex,

Proof. The lower bound $\gamma_{tI}(G)-\gamma(G)\leq \gamma_t(G)$ was given in ^[14]. Now, we observe that any $\gamma_{tI}(G)$-function is also a $\{2\}$-dominating function on $G$. This implies that $\gamma_{\{2\}}(G)\leq \gamma_{tI}(G)$. We only need to prove that $\gamma_t(G)\leq \gamma_{\{2\}}(G)$. Let $f(V_0, V_1, V_2)$ be a $\gamma_{\{2\}}(G)$-function. Let $D\subseteq V(G)$ be a set of minimum cardinality among all the sets satisfying the following properties.

${\rm (i)}$ $V_1\cup V_2\subseteq D$.

${\rm (ii)}$ $N(x)\cap D\neq \emptyset$ for every $x\in V_2$.

We claim that $D$ is a total dominating set of $G$. It follows from the definition of $f$ and (i) that $D$ is a dominating set of $G$. Now, let $v\in D$. If $v\in D\setminus V_2$, then we have that $|N(v)\cap D|\geq |N(v)\cap (V_1\cup V_2)|\geq 1$ by the definition of $f$. Otherwise, if $v\in D\cap V_2$, then $|N(v)\cap D|\geq 1$ by (ii). Hence, $D$ is a total dominating set of $G$, as desired. Now, by the minimality of $|D|$, we observe that

as desired. Therefore, the proof is complete.

By the theorem above, we deduce that if $\gamma_{tI}(G) = \gamma_t(G)$, then $\gamma_{\{2\}}(G) = \gamma_t(G)$. However, the opposed is not necessarily true. For instance, the graphs $G$ with $\gamma(G) = 1$ and $\gamma_{tI}(G) = 3$ satisfy that $\gamma_{\{2\}}(G) = \gamma_t(G) = 2$. We state the following open problem.

Problem 2.8. Characterize the graphs $G$ satisfying the equality $\gamma_{\{2\}}(G) = \gamma_{t}(G).$

Now, we proceed to show that the bounds given in Theorem 2.7 are tight. For instance, for the graph $G$ given in Figure 1 we have that $\gamma_{tI}(G) = 6$, $\gamma_{\{2\}}(G) = \gamma_t(G) = 4$ and $\gamma(G) = 2$. Hence, $\gamma_{\{2\}}(G) = \gamma_t(G) = \gamma_{tI}(G)-\gamma(G)$.

Next, we present a well-known class of graphs which satisfies that $\gamma_{\{2\}}(G) = \gamma_{tI}(G)$. Given two graphs $G$ and $H$, the corona product graph $G\odot H$ is the graph obtained from $G$ and $H$, by taking one copy of $G$ and $|V(G)| = n(G)$ copies of $H$ and joining by an edge every vertex from the $i^{th}$-copy of $H$ with the $i^{th}$-vertex of $G$.

Theorem 2.9. ^[4] For any graph $G$ with no isolated vertex and any graph $H$,

Now, we proceed to characterize the graphs achieving the trivial bounds. Before, we need to cite the following theorem.

Theorem 2.10. ^[14] Let $G$ be a nontrivial connected graph. Then $\gamma_{tI}(G) = n(G)$ if and only if $G$ is isomorphic to the path $P_3$ or $G'\odot K_1$ for some connected graph $G'$.

Proposition 2.11. For any graph $G$ with no isolated vertex,

Furthermore,

${\rm (i)}$ $\gamma_{\{2\}}(G) = 2$ if and only if $\gamma(G) = 1$. ^[4]

${\rm (ii)}$ $\gamma_{\{2\}}(G) = 3$ if and only if $\gamma_{\times 2}(G) = \gamma(G)+1 = 3$. ^[4]

${\rm (iii)}$ $\gamma_{\{2\}}(G) = 4$ if and only if $\gamma_{\times 2}(G) = 4$ or $\gamma(G) = 2$ and $\gamma_{\times 2}(G)\geq 4$. ^[4]

${\rm (iv)}$ $\gamma_{\{2\}}(G) = n(G)$ if and only if every component of $G$ is isomorphic to the corona graph $G'\odot K_1$, where $G'$ is any connected graph.

Proof. The trivial bounds directly follows from Theorem 2.7 and the fact that $\gamma_t(G)\geq 2$ and $\gamma_{tI}(G)\leq n(G)$, i.e.,

In order to conclude the proof, we only need to prove (iv). If $\gamma_{\{2\}}(G) = n(G)$, then it follows from the previous inequality chain that $\gamma_{tI}(G) = n(G).$ Hence, by Theorem 2.10 and the fact that $\gamma_{\{2\}}(P_3) = 2 < n(P_3)$, we conclude that every component of $G$ is isomorphic to the corona graph $G'\odot K_1$, where $G'$ is any connected graph. The other implication is straightforward to see. Therefore, the proof is complete.

The next result, which is a direct consequence of the characterizations exposed in Proposition 2.11, provides exact formulas for the $\{2\}$-domination number of join graphs. Recall that, given two disjoint graphs $G_1$ and $G_2$, the join graph $G_1+G_2$ is the graph obtained from $G_1$ and $G_2$, with vertex set $V(G_1+G_2) = V(G_1)\cup V(G_2)$ and edge set $E(G_1+G_2) = E(G_1)\cup E(G_2)\cup \{uv: u\in V(G_1), v\in V(G_2)\}$.

Theorem 2.12. For any graphs $G_1$ and $G_2$,

Proof. First, we notice that $\gamma(G_1+G_2)\leq 2$. Hence, Theorem 2.1 leads to $\gamma_{\{2\}}(G_1+G_2)\leq 2\gamma(G_1+G_2)\leq 4$. By Proposition 2.11-(i) and the fact that $\gamma(G_1+G_2) = 1$ if and only if $\min\{\gamma(G_1), \gamma(G_2)\} = 1$, we observe that

So, assume now that $\gamma(G_1+G_2) = 2$. This implies that $\min\{\gamma(G_1), \gamma(G_2)\}\geq 2$. Hence, $\gamma_{\{2\}}(G_1+G_2)\in \{3, 4\}$. Moreover, it is easy to check that $\gamma_{\times 2}(G_1+G_2) = \gamma(G_1+G_2)+1 = 3$ if and only if $\min\{\gamma(G_1), \gamma(G_2)\} = 2$. Then, it follows from Proposition 2.11-(ii) that

which completes the proof.

3.   The particular case of trees

Studies on characterizing domination related parameters in trees have been very popular in the last decades. One can find in the literature several works showing all the trees satisfying diverse properties. For instance, and to just name a few of them, we refer to the works ^{[21,22,23,24,25,26,27]}. In this section, and using a similar approach to that used in the aforementioned works, we will show that the $\{2\}$-domination number of any tree is exactly twice the domination number. In order to prove this result, we first need to introduce some lemmas.

Lemma 3.1. For any tree $T$ of order $n(T)\geq 3$, there exists a $\gamma_{\{2\}}(T)$-function $f(V_0, V_1, V_2)$ such that $\mathcal{S}(T)\subseteq V_2$ and $\mathcal{L}(T)\subseteq V_0$.

Proof. Let $f(V_0, V_1, V_2)$ be a $\gamma_{\{2\}}(T)$-function such that $|V_2 \cap \mathcal{S}(T)|$ is maximum. Now, suppose that there exists a vertex $v\in \mathcal{S}(T)\setminus V_2$. This implies that $v\in V_1$ and so $N(v)\cap \mathcal{L}(T)\subseteq V_1$. Hence, the function $f'(V_0', V_1', V_2')$, defined by $V_0' = V_0\cup (N(v)\cap \mathcal{L}(T))$, $V_1' = V_1\setminus ((N(v)\cap \mathcal{L}(T))\cup\{v\})$ and $V_2' = V_2\cup \{v\}$, is a $\gamma_{\{2\}}(T)$-function such that $|V_2' \cap \mathcal{S}(T)| > |V_2 \cap \mathcal{S}(T)|$, which is a contradiction. Therefore, $\mathcal{S}(T)\subseteq V_2$ and as a consequence, $\mathcal{L}(T)\subseteq V_0$.

Lemma 3.2. Let $T$ be a tree obtained from any nontrivial tree $T'$ by attaching a path $P_2$ to a vertex $v\in \mathcal{S}(T')\cup \mathcal{SS}(T')$. Then $\gamma_{\{2\}}(T) = \gamma_{\{2\}}(T')+2$ and $\gamma(T) = \gamma(T')+1$.

Proof. Assume that $T$ is obtained from $T'$ by adding the path $uu_1$ and the edge $uv$, where $v\in \mathcal{S}(T')\cup \mathcal{SS}(T')$. Notice that any $\gamma(T')$-set can be extended to a dominating set of $T$ by adding the vertex $u$. Hence, $\gamma(T)\leq \gamma(T')+1$. Let $D$ be a $\gamma(T)$-set such that $\mathcal{S}(T)\subseteq D$ (of course, such a set $D$ exists by ^[23]). Since $v\in D$ or $(N(v)\cap D)\setminus \{u\}\neq \emptyset$, we observe that $D\setminus \{u\}$ is a dominating set of $T'$. Hence, $\gamma(T')+1\leq |D\setminus \{u\}|+1 = \gamma(T)$. Therefore, $\gamma(T) = \gamma(T')+1$, as desired.

Next, let $f(V_0', V_1', V_2')$ be a $\gamma_{\{2\}}(T')$-function. Notice that the function $f(V_0, V_1, V_2)$, defined by $V_0 = V_0'$, $V_1 = V_1'\cup \{u, u_1\}$ and $V_2 = V_2'$, is a $\{2\}$-dominating function on $T$. Hence, $\gamma_{\{2\}}(T)\leq \omega(f) = \gamma_{\{2\}}(T')+2$. Now, let $g(W_0, W_1, W_2)$ be a $\gamma_{\{2\}}(T)$-function which satisfies Lemma 3.1. Hence, $u_1\in W_0$ and $u\in W_2$. Since $v\in \mathcal{S}(T)$ or $(N(v)\cap \mathcal{S}(T))\setminus \{u\}\neq \emptyset$, we deduce that the function $g$ restricted to $V(T')$, is a ${\{2\}}$-dominating function on $T'$. Hence, $\gamma_{\{2\}}(T')+2\leq g(V(T'))+2 = \gamma_{\{2\}}(T)$. Therefore, $\gamma_{\{2\}}(T) = \gamma_{\{2\}}(T')+2$, which completes the proof.

Lemma 3.3. Let $T$ be a tree obtained from any nontrivial tree $T'$ by attaching a path $P_3$ to any vertex $v\in V(T')$. Then $\gamma_{\{2\}}(T) = \gamma_{\{2\}}(T')+2$ and $\gamma(T) = \gamma(T')+1$.

Proof. Assume that $T$ is obtained from $T'$ by adding the path $uu_1u_2$ and the edge $uv$, where $v\in V(T')$. Notice that any $\gamma(T')$-set can be extended to a dominating set of $T$ by adding the vertex $u_1$. Hence, $\gamma(T)\leq \gamma(T')+1$. Now, let $D$ be a $\gamma(T)$-set such that $D\cap \mathcal{L}(T) = \emptyset$ and $|N[u_1]\cap D|$ is minimum. It is easy to see that $u_1\in D$ and $u, u_2\notin D$, and so $D\setminus \{u_1\}$ is a dominating set of $T'$. Hence, $\gamma(T')+1\leq |D\setminus \{u_1\}|+1 = \gamma(T)$. Therefore, $\gamma(T) = \gamma(T')+1$, as desired.

Next, let $f(V_0', V_1', V_2')$ be a $\gamma_{\{2\}}(T')$-function. Notice that the function $f(V_0, V_1, V_2)$, defined by $V_0 = V_0'\cup \{u, u_2\}$, $V_1 = V_1'$ and $V_2 = V_2'\cup \{u_1\}$, is a $\{2\}$-dominating function on $T$. Hence, $\gamma_{\{2\}}(T)\leq \omega(f) = \gamma_{\{2\}}(T')+2$. Now, let $g(W_0, W_1, W_2)$ be a $\gamma_{\{2\}}(T)$-function such that $g(N[u_1])$ is minimum among all $\gamma_{\{2\}}(T)$-functions which satisfy Lemma 3.1. Hence, it is easy to check that $u, u_2\in W_0$ and $u_1\in W_2$, and so the function $g$ restricted to $V(T')$, is a ${\{2\}}$-dominating function on $T'$. Hence, $\gamma_{\{2\}}(T')+2\leq |g(V(T'))|+2 = \gamma_{\{2\}}(T)$. Therefore, $\gamma_{\{2\}}(T) = \gamma_{\{2\}}(T')+2$, which completes the proof.

We are now ready to prove that $\gamma_{\{2\}}(T) = 2\gamma(T)$ for any tree $T$.

Theorem 3.4. For any tree $T$, we have

Proof. First, we proceed to prove that $\gamma_{\{2\}}(T)\geq 2\gamma(T)$ by induction on the order of the trees. Let $T$ be any tree. We observe that if $\operatorname{diam}(T)\leq 3$, then it is easy to check that $\gamma_{\{2\}}(T)\geq 2\gamma(T)$. This establishes the base case. So assume that $\operatorname{diam}(T)\geq 4$ (notice $n(T) > 4$) and any tree $T'$ with $n(T') < n(T)$ satisfies $\gamma_{\{2\}}(T')\geq 2\gamma(T')$. Now, we root the tree $T$ at a leaf vertex $r$ belonging to a diametrical path in $T$. Let $h$ be a vertex such that $d(r, h) = \operatorname{diam}(G)$. Clearly, $h\in \mathcal{L}(T)$. Let $s$ be the parent of $h$, and let $v$ be the parent of $s$. We now proceed with the following claims.

Claim I. If $|N(s)|\geq 3$, then $\gamma_{\{2\}}(T)\geq 2\gamma(T)$.

Proof. Let $f(V_0, V_1, V_2)$ be a $\gamma_{\{2\}}(T)$-function which satisfies Lemma 3.1. Hence, $s\in V_2$ and $h\in V_0$. Let $T' = T-\{h\}$. Notice that $f$ restricted to $V(T')$ is a $\{2\}$-dominating function on $T'$, which implies that $\gamma_{\{2\}}(T) = \omega(f) = f(V(T'))\geq \gamma_{\{2\}}(T')$. Also, since $s\in \mathcal{S}(T')\cap \mathcal{S}(T)$, we deduce that $\gamma(T') = \gamma(T)$. Thus, by the previous inequalities and the induction hypothesis we obtain that

which completes the proof of Claim I. $\quad (\diamond)$

Claim II. If $|N(s)| = 2$ and $|N(v)|\geq 3$, then $\gamma_{\{2\}}(T)\geq 2\gamma(T)$.

Proof. Let $T' = T-\{h, s\}$. Notice that $v\in \mathcal{S}(T')\cup \mathcal{SS}(T')$. Hence, by Lemma 3.2 we have that $\gamma_{\{2\}}(T) = \gamma_{\{2\}}(T')+2$ and $\gamma(T) = \gamma(T')+1$. Also, by the induction hypothesis we have that $\gamma_{\{2\}}(T')\geq 2\gamma(T')$. Therefore,

which completes the proof of Claim II. $\quad (\diamond)$

Claim III. If $|N(s)| = |N(v)| = 2$, then $\gamma_{\{2\}}(T)\geq 2\gamma(T)$.

Proof. Let $T' = T-\{h, s, v\}$. By Lemma 3.3 we have that $\gamma_{\{2\}}(T) = \gamma_{\{2\}}(T')+2$ and $\gamma(T) = \gamma(T')+1$. Also, by the induction hypothesis we have that $\gamma_{\{2\}}(T')\geq 2\gamma(T')$. Therefore,

which completes the proof of Claim III. $\quad (\diamond)$

Therefore, $\gamma_{\{2\}}(T)\geq 2\gamma(T)$, as desired. Finally, by Theorem 2.1 we have that $\gamma_{\{2\}}(T)\leq 2\gamma(T)$. Thus, $\gamma_{\{2\}}(T) = 2\gamma(T)$, which completes the proof.

4.   The particular case of lexicographic product graphs

The lexicographic product of two graphs $G$ and $H$ is the graph $G \circ H$ whose vertex set is $V(G \circ H) = V(G) \times V(H)$ and $(u, v)(x, y) \in E(G \circ H)$ if and only if $ux \in E(G)$ or $u = x$ and $vy \in E(H)$. Notice that for any $u\in V(G)$ the subgraph of $G\circ H$ induced by $\{u\}\times V(H)$ is isomorphic to $H$. For simplicity, we will denote this subgraph by $H_u$. Moreover, the neighbourhood of $(x, y)\in V(G)\times V(H)$ will be denoted by $N(x, y)$ instead of $N((x, y))$. Analogously, for any function $f$ on $G\circ H$, the image of $(x, y)$ will be denoted by $f(x, y)$ instead of $f((x, y))$.

Recently, Cabrera-Martínez et al. ^[4] showed 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$. Specifically, they show that $\gamma_{I}(G\circ H) = \gamma_{w}(G)$ (where $w\in \{2\}\times\{0, 1, 2\}^{l}$ and $l\in \{2, 3\}$) and the decision on whether the equality holds for specific values of $w_0, \dots, w_l$ depends on the value of the domination number of $H$. Later, the same authors ^[28] showed how the secure (total) domination number and the (total) weak Roman domination number of lexicographic product graphs $G\circ H$ are related to $\gamma^s_{w}(G)$ or $\gamma_{w}(G)$ (where $\gamma^s_{w}(G)$ represents the secure version of $\gamma_{w}(G)$, see ^[29]). These previous studies show an interesting way to study the domination parameters in lexicographic product graphs.

In such a sense, in this section we show how the $\{2\}$-domination number of $G\circ H$ is related to $\gamma_w(G)$. In particular, the decision on whether $w$ takes specific components depends on the value of $\gamma(H)$. For this purpose, we need to expose the following lemma.

Lemma 4.1. For any graph $G$ with no isolated vertex and any nontrivial graph $H$, there exists a $\gamma_{\{2\}}(G\circ H)$-function $f(V_0, V_1, V_2)$ satisfying that $f(V(H_x))\leq 2$ for every $x\in V(G)$.

Proof. Given a $\{2\}$-dominating function $f$ on $G\circ H$, define the set $E_f = \{x\in V(G): \, f(V(H_x))\geq 3\}$. Let $f(V_0, V_1, V_2)$ be a $\gamma_{\{2\}}(G\circ H)$-function such that $|E_f|$ is minimum among all $\gamma_{\{2\}}(G\circ H)$-functions. Suppose that $E_f\neq \emptyset$ and let $u\in E_f$, we consider the following two cases.

Case 1. $f(V(H_u))\geq 4$ or $f(V(H_u)) = 3$ and $\sum_{x\in N(u)}f(V(H_x))\geq 1$. In this case, let $u'\in N(u)$ such that $f(V(H_{u'}))$ is maximum among all vertices adjacent to $u$. So, if $f(V(H_u)) = 3$, then $f(V(H_{u'}))\geq 1$. Consider now the function $f': V(G)\times V(H)\rightarrow \{0, 1, 2\}$ defined on $G\circ H$ as follows.

● $f'(u, v) = f'(u', v) = 2$ and $f'(u, y) = f'(u', y) = 0$ for some $v\in V(H)$ and every $y\in V(H)\setminus \{v\}$;

● $f'(x, y) = f(x, y)$ for every $x\in V(G)\setminus \{u, u'\}$ and $y\in V(H)$.

Notice that $f'$ is a $\{2\}$-dominating function on $G\circ H$ with $\omega(f')\le \omega(f)$ and $|E_{f'}| < |E_f|$, which is a contradiction with the minimality of $|E_f|$.

Case 2. $f(V(H_u)) = 3$ and $f(V(H_x)) = 0$ for every vertex $x\in N(u)$. In this case, let $u'\in N(u)$. If there exists $v\in V(H)$ such that $f(u, v) = 2$, then there exists $v'\in N(v)$ such that $f(u, v') = 1$ because $f$ is a $\{2\}$-dominating function. Notice that the function $g$, defined by $g(u, v) = g(u, v') = g(u', v) = 1$ and $g(x, y) = f(x, y)$ for every $(x, y)\in V(G\circ H)\setminus \{(u, v), (u, v'), (u', v)\}$, is a $\{2\}$-dominating function on $G\circ H$ with $\omega(g) = \omega(f)$ and $|E_{g}| < |E_f|$, which is a contradiction with the minimality of $|E_f|$. Hence $V(H_u)\cap V_2 = \emptyset$, which implies that there exist $v, v', v''\in V(H)$ such that $f(u, v) = f(u, v') = f(u, v'') = 1$ and $f(x, y) = 0$ for every $(x, y)\in V(H_u)\setminus \{(u, v), (u, v'), (u, v'')\}$. Consider now the function $g': V(G)\times V(H)\rightarrow \{0, 1, 2\}$ defined on $G\circ H$ as follows.

● $g'(u, v) = g'(u, v') = g(u', v) = 1$ and $g'(u, v'') = 0$;

● $g'(x, y) = f(x, y)$ for every $(x, y)\in V(G\circ H)\setminus \{(u, v), (u, v'), (u, v''), (u', v)\}$.

By the definitions of $f$ and $g'$, one can see that $g'$ is a $\{2\}$-dominating function on $G\circ H$ with $\omega(g') = \omega(f)$ and $|E_{g'}| < |E_f|$, which is a contradiction with the minimality of $|E_f|$.

Therefore, from the two cases above, we deduce that $E_f = \emptyset$, i.e., $f(V(H_x))\leq 2$ for every $x\in V(G)$, which completes the proof.

Theorem 4.2. For any graph $G$ with no isolated vertex and any nontrivial graph $H$, we have

Proof. Let $f(V_0, V_1, V_2)$ be a $\gamma_{\{2\}}(G\circ H)$-function which satisfies Lemma 4.1. Define the function $g(W_0, W_1, W_2)$ on $G$ as follows.

Observe that $\gamma_{\{2\}}(G\circ H) = \omega(f) = \omega(g)$. Now, we proceed to prove that $g$ is a $\gamma_{(w_0, w_1, w_2)}(G)$-function. To prove this claim and find the values of $w_0$, $w_1$ and $w_2$, we differentiate the next three cases.

Case $1.$ $\gamma(H) = 1$. Let $u\in V(G)$. First, we assume that $u\in W_0$. Hence, $f(V(H_u)) = 0$, which implies that for any $v\in V(H)$ we obtain that $f(N(u, v)\setminus V(H_u))\geq 2$. So, $g(N(u))\geq 2$. Now, we assume that $u\in W_1$. By definition, there exists the unique vertex $v\in V(H)$ such that $f(u, v) = 1$. Since $\gamma(H) = 1$, for any $y\in V(H)\setminus \{v\}$, we have that $f(N(u, y)\setminus V(H_u))\geq 1$. Thus, we have $g(N(u))\geq 1$. Consequently, we have that $g$ is a $\{2\}$-dominating function on $G$, and so $\gamma_{\{2\}}(G)\leq \omega(g) = \omega(f) = \gamma_{\{2\}}(G\circ H)$.

On the other hand, notice that for any $\gamma_{\{2\}}(G)$-function $h(X_0, X_1, X_2)$ and any $\gamma(H)$-set $\{v\}$, the function $h'(X_0', X_1', X_2')$, defined by $X_1' = X_1\times \{v\}$, $X_2' = X_2\times \{v\}$ and $X_0' = V(G\circ H)\setminus(X_1'\cup X_2')$, is a $\{2\}$-dominating function on $G\circ H$. Hence, $\gamma_{\{2\}}(G\circ H)\leq \omega(h') = \omega(h) = \gamma_{\{2\}}(G)$. Therefore, if $\gamma(H) = 1$ then $\gamma_{\{2\}}(G\circ H) = \gamma_{\{2\}}(G)$.

Case $2.$ $\gamma(H) = 2$. Let $u\in V(G)$. As in Case 1 we conclude that $g(N(u))\geq 2$ for every vertex $u\in W_0$. Assume now that $u\in W_1$. By definition, there exists the unique vertex $v\in V(H)$ such that $g(u, v) = 1$. Since $\gamma(H) = 2$, we deduce that there exists a vertex $v'\in V(H)\setminus N[v]$ such that $f(N[(u, v')]\cap V(H_u)) = 0$. This implies that $f(N(u, v)\setminus V(H_{u}))\geq 2$. Hence, $g(N(u))\geq 2$ for every vertex $u\in W_1$. Finally, we assume that $u\in W_2$. Since $\gamma(H) = 2$, we observe that there exists $v\in V(H)$ such that either $f(u, v) = 0$ and $f(N(u, v)\cap V(H_u))\leq 1$ or $f(u, v) = 1$ and $f(N(u, v)\cap V(H_u)) = 0$. This implies that $f(N(u, v)\setminus V(H_u))\geq 1$, and as a consequence, $g(N(u))\geq 1$. Therefore, $g$ is a $(2, 2, 1)$-dominating function on $G$, and so $\gamma_{(2, 2, 1)}(G)\leq \omega(g) = \omega(f) = \gamma_{\{2\}}(G\circ H)$.

On the other hand, given any $\gamma_{(2, 2, 1)}(G)$-function $h(X_0, X_1, X_2)$ and any $\gamma(H)$-set $D = \{v, v'\}$, we can define the function $h'(X_0', X_1', X_2')$ on $G\circ H$ by making $X_1' = (X_1\times \{v\})\cup (X_2\times D)$, $X_2' = \emptyset$ and $X_0' = V(G\circ H)\setminus X_1'$. It is straightforward to check that $h'$ is a $(2, 2, 1)$-dominating function on $G\circ H$. Hence, $\gamma_{\{2\}}(G\circ H)\leq \omega(h') = \omega(h) = \gamma_{(2, 2, 1)}(G)$, and therefore, if $\gamma(H) = 2$ then $\gamma_{\{2\}}(G\circ H) = \gamma_{(2, 2, 1)}(G)$.

Case $3.$ $\gamma(H)\ge 3$. First, we notice that for every $u\in V(G)$, there exists a vertex $v\in V(H)$ such that $f(N[(u, v)]\cap V(H_u)) = 0$. This implies that $f(N(u, v)\setminus V(H_{u}))\geq 2$. Hence, $g(N(u))\geq 2$ for every vertex $u\in V(G)$, which implies that $g$ is a $(2, 2, 2)$-dominating function on $G$. Therefore, $\gamma_{(2, 2, 2)}(G)\leq \omega(g) = \omega(f) = \gamma_{\{2\}}(G\circ H)$.

On the other hand, let $h(X_0, X_1, X_2)$ be a $\gamma_{(2, 2, 2)}(G)$-function and let $v\in V(H)$. Notice that the function $h'(X_0', X_1', X_2')$, defined by $X_1' = X_1\times \{v\}$, $X_2' = X_2\times \{v\}$ and $X_0' = V(G\circ H)\setminus (X_1'\cup X_2')$, is a $(2, 2, 2)$-dominating function on $G\circ H$. Thus, $\gamma_{\{2\}}(G\circ H)\leq \omega(h') = \omega(h) = \gamma_{(2, 2, 2)}(G)$, and so if $\gamma(H)\geq 3$ then $\gamma_{\{2\}}(G\circ H) = \gamma_{(2, 2, 2)}(G)$.

According to the three cases above, the result follows.

5.   Conclusions

In this paper, we have studied the $\{2\}$ domination number of a graph. Among the main contributions, we emphasize the following.

● We have shown the close relationship that exists between the $\{2\}$ domination number and other domination parameters such as (total) domination number and (total) Italian domination number.

● We have provided closed formulas on the $\{2\}$ domination number for some families of graphs.

● In a specific section, we focused on the study of the parameter in lexicographic product graphs.

We next propose some open problems which we consider to be interesting:

(i) Characterize the graphs $G$ such that $\gamma_{\{2\}}(G) = \gamma_{tI}(G)$ and $\gamma_{\{2\}}(G) = \gamma_{tI}(G)-\gamma(G)$.

(ii) Settle Problem 2.8.

(iii) We propose to study the $\{2\}$ domination number of other product graphs.

Conflict of interest

We declare no conflict of interest.