Further results on the total Italian domination number of trees

1.   Introduction

In this article, we consider $G$ as a simple graph of order $n(G) = |V(G)|$ and size $m = |E(G)|$. Given a vertex $v$ of $G$, $N(v) = \{x\in V(G): xv\in E(G)\}$ and $N[v] = N(v)\cup \{v\}$. The degree of $v$ in $G$, denoted by $deg_G(v)$, is the cardinality of $N(v)$. A vertex $v\in V(G)$ is a leaf if $\deg_G(v) = 1$, and $v$ is a support vertex 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. The values $l(G)$ and $s(G)$ represent the number of leaves and the number of support vertices, respectively, i.e., $l(G) = |\mathcal{L}(G)|$ and $s(G) = |\mathcal{S}(G)|$. A set of vertices $D\subseteq V(G)$ is a dominating set of $G$ if $|N(x)\cap D|\geq 1$ for every vertex $x\in V(G)\setminus D$. The domination number of $G$, denoted by $\gamma(G)$, is the minimum cardinality among all dominating sets of $G$. A $\gamma(G)$-set is a dominating set of $G$ of cardinality $\gamma(G)$.

For an arbitrary subset $\mathcal{P}$ of nonnegative reals, a function $f:V(G) \rightarrow \mathcal{P}$ is a dominating function on $G$ if the set $\{x\in V(G): f(x) > 0\}$ is a dominating set of $G$. In 1998, the authors of the books ^[1,2] exposed some of the first studied varieties of dominating functions in graphs. Similarly, in the last two decades, dominating functions have been topics of interest within domination theory in graphs. In particular, the study of the Roman dominating functions and their variants stands out.

Recently, a new variant of Roman domination, called total Italian domination number, was introduced in ^[3] and independently in ^[4], under the name of total Roman $\{2\}$-domination number. For a graph $G$ with no isolated vertex, a total Italian dominating function (TIDF) on $G$ is a dominating function $f: V(G)\rightarrow \{0, 1, 2\}$ which satisfies the following two conditions.

● Every vertex $x\in V(G)$ for which $f(x) = 0$ satisfies that $\sum_{u\in N(x)}f(u)\geq 2$.

● The subgraph induced by the set $\{x\in V(G): f(x)\geq 1\}$ has no isolated vertex.

Observe that the function $f$ generates three sets $W_0$, $W_1$ and $W_2$, where $W_i = \{x\in V(G) : f(x) = i\}$ for $i \in \{0, 1, 2\}$. In such a sense, we write $f(W_0, W_1, W_2)$ so as to refer to the TIDF $f$. Sometimes we will introduce the notation $f(V_0, V_1, V_2)$, with vertex sets $V_i$ instead of vertex sets $W_i$, in order to distinguish some functions. Given a set $D\subseteq V(G)$, $f(D) = \sum_{x\in D}f(x)$. The total Italian domination number of $G$, denoted by $\gamma_{tI}(G)$, is the minimum weight $\omega(f) = \sum_{x\in V(G)}f(x) = |W_1|+2|W_2|$ among all TIDFs $f(W_0, W_1, W_2)$ on $G$. For simplicity, a TIDF $f$ of weight $\omega(f) = \gamma_{tI}(G)$ will be called a $\gamma_{tI}(G)$-function.

The problem of computing the total Italian domination number of a graph is NP-hard ^[3,4]. This suggests obtaining closed formulas or giving tight bounds for this parameter. Further combinatorial results on total Italian domination can be found for example, in ^[5,6,7,8]. In ^[4,5] some results for the case of trees were presented. For instance, in ^[4] the authors showed that $\left\lceil \frac{2(n(T)-l(T)+3)}{3} \right\rceil\leq \gamma_{tI}(T)\leq \frac{3n(T)+2s(T)}{4}$ for any tree of order $n(T)\geq 4$. Moreover, in ^[5] the authors characterized the trees $T$ with $\gamma_{tI}(T) = 3\gamma(T)$.

In this paper we continue with the study of this parameter in trees. In such a sense, our main goal is to provide some new tight bounds on the total Italian domination number in trees. The article is organized as follows. In Section 2 we introduce some additional concepts and notation needed to develop the remaining sections. Sections 3 and 4 are devoted to obtaining new lower and upper bounds on the total Italian domination number in terms of order, domination number, number of support vertices and number of leaves of a tree. In particular, we show that if $T$ is a tree of order $n(T)\geq 2$, then the following inequality chains hold.

(ⅰ) $2\gamma(T)\leq \gamma_{tI}(T)\leq n(T)-\gamma(T)+s(T)$.

(ⅱ) $(n(T)+\gamma(T)+s(T)-l(T)+1)/2\leq \gamma_{tI}(T)\leq (n(T)+\gamma(T)+l(T))/2$.

In addition, we show some classes of graphs for which the bounds above are achieved. We end with a concluding remark section, where we provide two interesting consequences derived from the new bounds given and propose some open problems.

2.   Additional concepts and notation

We first present additional necessary terminology and notation. Given a graph $G$ and a set $D\subseteq V(G)$, $N(D) = \cup_{x\in D} N(x)$ and $N[D] = N(D)\cup D$, respectively. As usual, by $G$-$D$ we denote the graph obtained from $G$ by removing all the vertices of $D$ and all the edges incident with a vertex in $D$. In addition, let $\mathcal{S}_s(G) = \{x\in \mathcal{S}(G): |N(x)\cap \mathcal{L}(G)|\geq 2\}$. Moreover, a vertex $x\in V(G)$ is a semi-support vertex if $x\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)$. The minimum and maximum degrees of a graph $G$ will be denoted by $\delta(G)$ and $\Delta(G)$, respectively. For any two vertices $x, y\in V(G)$, the distance $d(x, y)$ between $x$ and $y$ is the minimum length of a $x-y$ path. The diameter of $G$, denoted by $diam(G)$, is the maximum distance among all pairs of vertices in $G$.

Given a rooted tree $T$ (with root $r$) and a vertex $v\in V(T)\setminus\{r\}$, we say that a descendant of $v$ is a vertex $u\in V(T)$ such that the unique $r-u$ path contains $v$. The set of descendants of $v$ is denoted by $D[v]$. The maximal subtree at $v$, denoted by $T_v$, is the subtree of $T$ induced by $D[v]$.

A set $D\subseteq V(G)$ is said to be a double dominating set (DDS) of $G$ if $|N[x]\cap D|\geq 2$ for every vertex $x\in V(G)$. The double domination number of $G$, denoted by $\gamma_{\times 2}(G)$, is the minimum cardinality among all DDSs of $G$. A $\gamma_{\times 2}(G)$-set is a DDS of $G$ of cardinality $\gamma_{\times 2}(G)$. This parameter was introduced in ^[9] by Harary and Haynes, and has been extensively studied. For instance, we cite the recent works ^{[10,11,12,13,14]}. In addition, we observe that a set $D\subseteq V(G)$ is a DDS of $G$ if and only if there exists a TIDF $f(W_0, W_1, W_2)$ such that $W_1 = D$ and $W_2 = \emptyset$. Therefore, and by definition, it follows that $\gamma_{tI}(G)\leq \gamma_{\times 2}(G)$.

Any other definitions that are of interest, will be introduced where needed.

3.   Bounds in terms of order, domination number and number of support vertices

The main goal of this section is to show that for any tree $T$ of order $n(T)\geq 2$,

The previous inequality chain will be deduced as a direct consequence of Theorem 3.2 and Corollary 3.5. Before, we shall need to introduce the following useful lemma.

Lemma 3.1. If $G$ is a connected graph of order at least four, then there exists a $\gamma_{tI}(G)$-function $g(W_0, W_1, W_2)$ such that the following conditions hold.

${\rm (a)}$ $\mathcal{S}_s(G)\subseteq W_2$ and $|N(x)\cap\mathcal{L}(G)\cap W_0|\geq |N(x)\cap\mathcal{L}(G)|-1$ for every $x\in \mathcal{S}_s(G)$.

${\rm (b)}$ $V_{\leq 2}(G)\subseteq W_0\cup W_1$, where $V_{\leq 2}(G) = \{x\in V(G): \deg_G(x)\leq 2\}$.

Proof. Among all the $\gamma_{tI}(G)$-functions $f(V_0, V_1, V_2)$ satisfying that $|\mathcal{S}_s(G)\cap V_2|$ is maximum, let $g(W_0, W_1, W_2)$ be a function such that $|V_{\leq 2}(G)\cap W_2|$ is minimum.

We first suppose that there exists a vertex $v\in \mathcal{S}_s(G)\setminus W_2$. This implies that $v\in W_1$ and $N(v)\cap \mathcal{L}(G)\subseteq W_1$. Now, we consider the function $g'(W_0', W_1', W_2')$ defined by $g'(v) = 2$, $g'(N(v)\cap \mathcal{L}(G)) = g(N(v)\cap \mathcal{L}(G))-1$ and $g'(x) = g(x)$ whenever $x\in V(G)\setminus (\{v\}\cup (N(v)\cap \mathcal{L}(G)))$. Since $|N(v)\cap \mathcal{L}(G)|\geq 2$, it follows that $g'$ is a $\gamma_{tI}(G)$-function such that $|\mathcal{S}_s(G)\cap W_2'| > |\mathcal{S}_s(G)\cap W_2|$, a contradiction. Therefore, $\mathcal{S}_s(G)\subseteq W_2$. In addition, and as an immediate consequence of the previous inclusion, we have that $|N(x)\cap\mathcal{L}(G)\cap W_0|\geq |N(x)\cap\mathcal{L}(G)|-1$ for every $x\in \mathcal{S}_s(G)$. Hence, condition (a) follows.

Finally, we proceed to prove (b). Let $x\in V_{\leq 2}(G)$. If $x\in \mathcal{L}(G)$, then it is straightforward that $x\in W_0\cup W_1$. Now, we assume that $N(x) = \{y, z\}$ and without loss of generality, suppose that $g(y)\leq g(z)$. If $g(z) = 0$ then $g(y) = 0$, and as a consequence, we have that $N(x)\subseteq W_0$, which contradicts the fact that $N(x)\cap (W_1\cup W_2)\neq \emptyset$ by definition. Hence, $g(z) > 0$. If $x\in W_2$ then $y\in W_0$, which implies that the function $h(V_0', V_1', V_2')$ defined by $h(x) = h(y) = 1$ and $h(u) = g(u)$ whenever $u\in V(G)\setminus \{x, y\}$, is a $\gamma_{tI}(G)$-function such that $|\mathcal{S}_s(G)\cap V_2'| = |\mathcal{S}_s(G)\cap W_2|$ (observe that $x\notin \mathcal{S}_s(G)$ because $|N(x)| = 2$ and $n(G)\geq 4$) and $|V_{\leq 2}(G)\cap V_2'| = |V_{\leq 2}(G)\cap (W_2\setminus \{x\})| < |V_{\leq 2}(G)\cap W_2|$, a contradiction. Hence, $x\in W_0\cup W_1$, which implies that $V_{\leq 2}(G)\subseteq W_0\cup W_1$. Therefore, the proof is complete.

In order to prove the next result, we need to introduce the following definition. A set $S\subseteq V(G)$ is a $2$-packing set of $G$ if $N[x]\cap N[y] = \emptyset$ for every pair of different vertices $x, y\in S$. The $2$-packing number of $G$, denoted by $\rho(G)$, is the maximum cardinality among all $2$-packing sets of $G$.

Theorem 3.2. For any connected graph $G$ of order at least two,

Furthermore, for any tree $T$ of order $n(T)\geq 2$,

Proof. If $n(G)\in\{2, 3\}$, then it is straightforward that $\gamma_{tI}(G)\geq \gamma(G)+s(G)$. From now on, we assume that $n(G)\geq 4$. Let $g(W_0, W_1, W_2)$ be a $\gamma_{tI}(G)$-function defined as in the proof of Lemma 3.1. Hence, $g$ satisfies the conditions given in Lemma 3.1. As $\mathcal{S}(G)\subseteq W_1\cup W_2$ and $|\mathcal{S}_s(G)\cap W_2|$ is maximum, then it is easy to deduce the following conditions.

(ⅰ) $\mathcal{L}(G)\subseteq W_0\cup W_1$.

(ⅱ) $|N(x)\cap \mathcal{L}(G)\cap W_1|\leq 1$ for every vertex $x\in \mathcal{S}(G)$.

By the previous conditions and the fact that $\mathcal{S}(G)\subseteq W_1\cup W_2$, we have that $|\mathcal{S}(G)\cap W_1|\leq |\mathcal{L}(G)\cap W_1|$ and that $W_2\cup (W_1\setminus \mathcal{L}(G))$ is a dominating set of $G$. Therefore,

as desired. Now, let $T$ be any tree of order at least two and let $S$ be a $2$-packing set of $T$ of cardinality $\rho(T)$. From any $\gamma_{tI}(T)$-function $f$, it follows that $f(N[x])\geq 2$ for every $x\in V(G)$. Since $N[x]\cap N[y] = \emptyset$ for every pair of different vertices $x, y\in S$, we deduce that

Finally, the result follows due to the fact that $\gamma(T) = \rho(T)$ for any tree $T$ (see ^[15]).

Now, we consider the following family of trees. We say that a tree $T$ belongs to the family $\mathcal{T}$ if it satisfies one of the following two conditions.

● $T$ is a subdivided star, i.e., $T$ is a graph obtained from a star by subdividing every edge exactly once.

● $T$ can be obtained from a star $K_{1, n}$ by subdividing exactly $n-1$ edges at most twice.

The following theorem provides a lower bound for any tree $T$ with $s(T) = l(T)$. In addition, this result shows that the bounds given in Theorem 3.2 are achieved for any tree $T$ belongs to the family $\mathcal{T}$ previously defined.

Theorem 3.3. The following statements hold for any tree $T$ of order $n(T)\geq 2$ with $s(T) = l(T)$.

${\rm (ⅰ)}$ $\gamma_{tI}(T)\geq\gamma(T)+\Delta(T)$.

${\rm (ⅱ)}$ $\gamma_{tI}(T) = \gamma(T)+\Delta(T)$ if and only if $T\in \mathcal{T}$.

Proof. By Theorem 3.2 and the fact that $s(T) = l(T)\geq \Delta(T)$, it follows that $\gamma_{tI}(T)\geq \gamma(T)+s(T) = \gamma(T)+l(T)\geq\gamma(T)+\Delta(T)$. Hence, (ⅰ) follows. Now, we proceed to prove (ⅱ). First, we suppose that $\gamma_{tI}(T) = \gamma(T)+\Delta(T)$. From the previous inequality chain we obtain that $l(T) = \Delta(T)$ and that $\gamma_{tI}(T) = \gamma(T)+s(T)$. The equality $l(T) = \Delta(T)$ implies that $V(T)\setminus \{v\}\subseteq V_{\leq 2}(T)$, where $v\in V(T)$ is a vertex of maximum degree. Let $g(W_0, W_1, W_2)$ be a $\gamma_{tI}(T)$-function which satisfies Lemma 3.1 (notice that $n(T)\geq 4$ because $s(T) = l(T)$). Thus, $\mathcal{S}(T)\setminus \{v\}\subseteq V_{\leq 2}(T)\subseteq W_0\cup W_1$. In addition, as $\gamma_{tI}(T) = \gamma(T)+s(T)$, then we have equalities through the inequality chain given in the proof of Theorem 3.2. In particular, we have that $|W_2\cup (W_1\setminus \mathcal{L}(T))| = \gamma(T)$, which implies that $D = W_2\cup (W_1\setminus \mathcal{L}(T))$ is a $\gamma(T)$-set. In order to deduce that $T\in \mathcal{T}$, we first show that $d(v, h)\leq 3$ for every $h\in \mathcal{L}(T)$. For this purpose, we suppose that there exists a leaf $h'$ such that $d(v, h')\geq 4$. Let us consider the path $v = v_0v_1\cdots v_r = h'$ ($r\geq 4$). Since $V(T)\setminus \{v\}\subseteq V_{\leq 2}(T)$, it follows by Lemma 3.1 that $V(T)\setminus \{v\}\subseteq W_0\cup W_1$, and without loss of generality, we can assume that $v_r, v_{r-1}, v_{r-3}\in W_1$, $v_{r-2}\in W_0$ and $v_{r-4}\in W_1\cup W_2$. Hence, $D\setminus \{v_{r-3}\}$ is a dominating set of $T$ of cardinality $|D|-1 = \gamma(T)-1$, a contradiction. Therefore, $d(v, h)\leq 3$ for every $h\in \mathcal{L}(T)$, as required. Now, we suppose that $T$ is not a subdivided star and that $v\notin \mathcal{S}(T)$. Hence, there exists a path $vv_1v_2v_3$ with $v_3\in \mathcal{L}(T)$. As above, and without loss of generality, we can assume that $v\in W_1\cup W_2$ and that $v_{1}\in W_0$. Since $\mathcal{S}(T)\subseteq W_1$ and $N(v)\cap W_1\neq \emptyset$, it follows that $D\setminus \{v\}$ is a dominating set of $T$ of cardinality $|D|-1 = \gamma(T)-1$, a contradiction. Therefore, either $T$ is a subdivided star or $T$ can be obtained from a star $K_{1, n}$ by subdividing exactly $n-1$ edges at most twice (recall that $s(T) = l(T)$). That is, $T\in \mathcal{T}$, as required. Finally, it is straightforward to observe that if $T\in \mathcal{T}$, then $\gamma_{tI}(T) = \gamma(T)+\Delta(T)$.

Theorem 3.4. If $T$ is a tree of order $n(T)\geq 2$, then

Proof. Let $S$ be a $2$-packing set of $T$ of cardinality $\rho(T)$ such that $|S\cap \mathcal{L}(T)|$ is maximum. By the maximality of $|S\cap \mathcal{L}(T)|$, it follows that $|N(x)\cap \mathcal{L}(T)\cap S| = 1$ for every $x\in \mathcal{S}(T)$, which implies that $|S\cap \mathcal{L}(T)| = |\mathcal{S}(T)|$. Let $D = (V(T)\setminus S)\cup \mathcal{L}(T)$. Observe that $|D| = n(T)-|S|+|S\cap \mathcal{L}(T)| = n(T)-\rho(T)+s(T)$. Now, we proceed to prove that $D$ is a DDS of $T$. As $V(T)\setminus D\subseteq S\setminus \mathcal{L}(T)$, it is easy to observe that $|N(x)\cap D|\geq 2$ for any vertex $x\in V(T)\setminus D$. Now, if $x\in D$, then $N(x)\cap D\neq \emptyset$ because $N(x)\not\subseteq S$. Hence, $D$ is a DDS of $T$, as desired. Therefore, $\gamma_{\times 2}(T)\leq |D| = n(T)-\rho(T)+s(T)$. Finally, the result follows due to the fact that $\gamma(T) = \rho(T)$ for any tree $T$ (see ^[15]).

The following result is an immediate consequence of the previous theorem and the fact that $\gamma_{tI}(T)\leq \gamma_{\times 2}(T)$ for any nontrivial tree $T$.

Corollary 3.5. If $T$ is a tree of order $n(T)\geq 2$, then

To see the tightness of the bounds given in Theorem 3.4 and Corollary 3.5 we consider for instance the path $P_{3k+1}$ with $k\geq 1$. For this particular tree, it is easy to deduce that $\gamma_{\times 2}(P_{3k+1}) = \gamma_{tI}(P_{3k+1}) = 2k+2 = n(P_{3k+1})-\gamma(P_{3k+1})+s(P_{3k+1})$.

4.   Bounds in terms of order, domination number, number of support vertices and number of leaves

The main goal of this section is to show that for any tree $T$ of order $n(T)\geq 2$,

The previous upper bound is a direct consequence of the well-known relationship $\gamma_{tI}(T)\leq \gamma_{\times 2}(T)$ and the inequality $\gamma_{\times 2}(T)\leq (n(T)+\gamma(T)+l(T))/2$ given by Cabrera-Martínez in ^[10]. In order to deduce the lower bound, we first need to state the following useful lemmas.

Lemma 4.1. ^[16] The following statements hold for any tree $T$ of order $n(T)\geq 2$.

${\rm (ⅰ)}$ If $T$ is obtained from any nontrivial tree $T'$ by attaching a path $P_2$ to any vertex $u\in \mathcal{S}(T')\cup \mathcal{SS}(T')$, then $\gamma(T) = \gamma(T')+1$.

${\rm (ⅱ)}$ If $T$ is obtained from any nontrivial tree $T'$ by attaching a path $P_3$ to any vertex $u\in V(T')$, then $\gamma(T) = \gamma(T')+1$.

Lemma 4.2. If $T$ is a tree obtained from any nontrivial tree $T'$ by attaching a path $P_3$ to any vertex $u\in V(T')$, then

Proof. Let $T$ be a tree obtained from $T'$ by adding the path $u_{d-1}u_{d}u_{d+1}$ and the edge $uu_{d-1}$, where $u\in V(T')$. By Lemma 3.1-(b) and the fact that $u_{d}\in \mathcal{S}(T)$, $u_{d+1}\in \mathcal{L}(T)$ and $u_{d-1}\in V_{\leq 2}(T)$, there exists a $\gamma_{tI}(T)$-function $f$ such that $f(u_{d}) = f(u_{d+1}) = 1$ and $f(u_{d-1})\leq 1$. We next define a function $f'$ on $T'$ as follows.

${\rm (a)}$ If $f(u_{d-1}) = 0$, then $f'(x) = f(x)$ whenever $x\in V(T')$.

${\rm (b)}$ If $f(u_{d-1}) = 1$ and $f(u) = 0$, then $f'(u) = 1$ and $f'(x) = f(x)$ whenever $x\in V(T')\setminus \{u\}$.

${\rm (c)}$ If $f(u_{d-1}) = 1$ and $f(u) > 0$, then $f'(u') = 1$ for some $u'\in N(u)\setminus \{u_{d-1}\}$ and $f'(x) = f(x)$ whenever $x\in V(T')\setminus \{u'\}$.

It is straightforward that the function $f'$, defined through any of the three previous options, is a TIDF on $T'$ with weight $\omega(f)-2$. Hence, $\gamma_{tI}(T')+2\leq \omega(f')+2 = \omega(f) = \gamma_{tI}(T)$, as desired.

Theorem 4.3. If $T$ is a tree of order $n(T)\geq 2$, then

Proof. We proceed by applying induction on the order of $T$. If $n(T)\in \{2, 3\}$, then it is straightforward that $\gamma_{tI}(T)\geq (n(T)+\gamma(T)+s(T)-l(T)+1)/2.$ These particular cases establish the base cases. Let $T$ be a tree of order at least four, and $P = u_1u_2\cdots u_{d+1}$ be a diametrical path in $T$, where $d = diam(T)$. Observe that $u_1, u_{d+1}\in \mathcal{L}(T)$. From now on, we consider that each tree $T'$ with $n(T') < n(T)$ satisfies that $\gamma_{tI}(T')\geq (n(T')+\gamma(T')+s(T')-l(T')+1)/2.$ Now, we differentiate the following cases.

Case 1. $\deg_T(u_d)\geq 3$. In this case, we consider that $T' = T-\{u_{d+1}\}$. Let $g(W_0, W_1, W_2)$ be a $\gamma_{tI}(T)$-function that satisfies the conditions of Lemma 3.1. By the condition (a) it follows that $u_d\in W_2$ and, without loss of generality, we can assume that $u_{d+1}\in W_0$. So, the function $g$ restricted to $V(T')$ is a TIDF on $T'$. Hence, $\gamma_{tI}(T')\leq g(V(T')) = \omega(g)-g(u_{d+1}) = \gamma_{tI}(T)$. In addition, as there exists a $\gamma(T)$-set containing no leaves, it is straightforward that $\gamma(T') = \gamma(T)$. Thus, by the inequalities above, the induction hypothesis and the fact that $n(T) = n(T')+1$, $s(T) = s(T')$ and $l(T) = l(T')+1$, we have the following desired result.

As can be seen from the proof above, the position of vertex $u_d\in \mathcal{S}(T)$ is not relevant. Hence, we may henceforth assume that $\mathcal{S}_s(T) = \emptyset$.

Case 2. $\deg_T(u_d) = 2$ and $\deg_T(u_{d-1})\geq 3$. Let $T' = T-\{u_{d+1}, u_d\}$. Let $g(W_0, W_1, W_2)$ be a $\gamma_{tI}(T)$-function such that $|W_1\cap \mathcal{L}(T)|$ is maximum.

Subcase 2.1. The function $g$ restricted to $V(T')$ is a TIDF on $T'$. As $g(u_{d+1})+g(u_d) = 2$, it follows that $\gamma_{tI}(T')\leq g(V(T')) = \omega(g)-(g(u_{d+1})+g(u_d)) = \gamma_{tI}(T)-2$. Also, as $\deg_T(u_{d-1})\geq 3$, it follows that $u_{d-1}\in \mathcal{S}(T')\cup \mathcal{SS}(T')$, which leads to $\gamma(T) = \gamma(T')+1$ by Lemma 4.1-(ⅰ). Thus, by the inequalities above, the induction hypothesis and the fact that $n(T) = n(T')+2$, $s(T) = s(T')+1$ and $l(T) = l(T')+1$, we have the following desired result.

Subcase 2.2. The function $g$ restricted to $V(T')$ is not a TIDF on $T'$. Let us observe that $N(u_{d-1})\setminus \{u_d, u_{d-2}\}\subset \mathcal{S}(T)\cup \mathcal{L}(T)$ and $u_{d-1}\notin \mathcal{S}_s(T)$. If $\deg_T(u_{d-1})\geq 4$ or $g(u_{d-1}) = 1$, then $g(N(u_{d-1})\setminus \{u_d, u_{d-2}\}) > 0$, and as a consequence, we obtain that $g$ restricted to $V(T')$ is a TIDF on $T'$, a contradiction. Therefore, $\deg_T(u_{d-1}) = 3$ and $g(u_{d-1})\neq 1$.

First, we consider that $g(u_{d-1}) = 0$. In this case, it follows that $u_{d-1}\in \mathcal{SS}(T)$, $|V(T_{u_{d-1}})| = 5$ and $V(T_{u_{d-1}})\setminus \{u_{d-1}\}\subseteq W_1$ (recall that $|W_1\cap \mathcal{L}(T)|$ is maximum). Let $T'' = T-V(T_{u_{d-1}})$. Notice that $g$ restricted to $V(T'')$ is a TIDF on $T''$, which implies that $\gamma_{tI}(T'')\leq g(V(T'')) = \omega(g)-g(V(T_{u_{d-1}})) = \gamma_{tI}(T)-4$. Also, it is straightforward that $\gamma(T)\leq\gamma(T'')+2$. Thus, by the inequalities above, the induction hypothesis and the fact that $n(T) = n(T'')+5$, $s(T)\leq s(T'')+2$ and $l(T)\geq l(T'')+1$, we have the following desired result.

Finally, we consider that $g(u_{d-1}) = 2$. This implies that $u_{d-1}\in \mathcal{S}(T)$, $|V(T_{u_{d-1}})| = 4$ and $u_{d}, u_{d+1}\in W_1$. If $g(N[u_{d-2}]\setminus \{u_{d-1}\}) > 0$, then the function $g'(W_0', W_1', W_2')$, defined as $g'(x) = 1$ whenever $x\in V(T_{u_{d-1}})$ and $g'(x) = g(x)$ otherwise, is a $\gamma_{tI}(T)$-function satisfying that $|W_1'\cap \mathcal{L}(T)| > |W_1\cap \mathcal{L}(T)|$, which is a contradiction. Therefore, $N[u_{d-2}]\setminus \{u_{d-1}\}\subseteq W_0$, which implies that $\deg_T(u_{d-2}) = 2$ as a consequence of the maximality of $|W_1\cap \mathcal{L}(T)|$. Let $T^* = T-V(T_{u_{d-2}})$. Since $u_{d-2}\in W_0$, it follows that $g$ restricted to $V(T^*)$ is a TIDF on $T^*$, which implies that $\gamma_{tI}(T^*)\leq g(V(T^*)) = \omega(g)-g(V(T_{u_{d-2}})) = \gamma_{tI}(T)-4$. Notice that $\gamma(T)\leq\gamma(T^*)+2$, $n(T) = n(T^*)+5$, $s(T)\leq s(T^*)+2$ and $l(T)\geq l(T^*)+1$. Hence, and proceeding analogously to the previous case ($g(u_{d-1}) = 0$), it follows the following desired inequality.

Case 3. $\deg_T(u_{d-1}) = \deg_T(u_{d}) = 2$. In this case, let $T' = T-\{u_{d-1}, u_d, u_{d+1}\}$. By Lemmas 4.2 and 4.1-(ⅱ) we have that $\gamma_{tI}(T)\geq\gamma_{tI}(T')+2$ and $\gamma(T) = \gamma(T')+1$, respectively. Now, we observe that $s(T')\geq s(T)-1$ and $l(T')\leq l(T)$. Next, we analyse the following two subcases.

Subcase 3.1. $s(T')\geq s(T)$ or $l(T')\leq l(T)-1$. In this subcase, by the previous inequalities, the induction hypothesis and the fact that $n(T) = n(T')+3$, we have the following desired result.

Subcase 3.2. $s(T') = s(T)-1$ and $l(T') = l(T)$. These previous conditions lead to $\deg_T(u_{d-2}) = 2$ and $u_{d-3}\in \mathcal{S}(T)$. Let $T'' = T-\{u_d, u_{d+1}\}$ and let $g(W_0, W_1, W_2)$ be a $\gamma_{tI}(T)$-function such that $|W_1\cap \{u_{d-2}, u_{d-1}, u_d, u_{d+1}\}|$ is maximum. Since $u_{d-3}\in W_1\cup W_2$, we can assume that $u_{d-2}, u_{d}, u_{d+1}\in W_1$ and $u_{d-1}\in W_0$. Notice that the function $g'$, defined by $g'(u_{d-1}) = 1$ and $g'(x) = g(x)$ if $x\in V(T'')\setminus \{u_{d-1}\}$, is a TIDF on $T''$. Therefore, $\gamma_{tI}(T'')+1\leq \omega(g')+1 = \omega(g) = \gamma_{tI}(T)$. In addition, we can deduce that $\gamma(T'') = \gamma(T)$ because $u_{d-3}\in \mathcal{S}(T)\cap \mathcal{S}(T'')$. By the previous inequalities, the induction hypothesis and the fact that $n(T) = n(T'')+2$, $s(T'') = s(T)$ and $l(T'') = l(T)$, we have the following desired result.

Therefore, and as consequence of the three cases above, the proof follows.

In order to show the sharpness of the lower bound given in Theorem 4.3, we need to define the next family of trees. Given an integer $r\geq 2$, the tree $G_r$ is constructed from the path $P_{2r+1} = v_1v_2\cdots v_{2r+1}$ and the path $P_1$ by taking one copy of $P_{2r+1}$ and $r+1$ copies of $P_1$ and adding edges between the vertex $v_{2i+1}$ and the $i$-th copy of $P_1$ with $i\in \{0, \ldots, r\}$. In Figure 1 we can show the tree $G_2$. Observe that $n(G_r) = 3r+2$, $\gamma(G_r) = s(G_r) = l(G_r) = r+1$ and $\gamma_{tI}(G_r) = 2r+2$. Therefore,

5.   Conclusions

In this article we studied the total Italian domination number of nontrivial trees. In particular, we obtained new lower and upper bounds on this domination parameter in terms of order, domination number, number of support vertices and number of leaves of a nontrivial tree. In addition, we discussed some extreme cases.

The problem of computing $\gamma_{tI}(T)$ for trees $T$ can be solved in polynomial time according to ^[4]. Nevertheless, through the relationships given in this article, new results can be obtained, as well as defining some new open problems. The following theorem provides two consequences derived from inequality chain (3.1) and the bound $\gamma(T)\geq (n(T)-l(T)+2)/3$ given in ^[17].

Theorem 5.1. The following statements hold for any tree $T$ of order $n(T)\geq 3$.

${\rm (ⅰ)}$ $\gamma(T)\leq \frac{n(T)+s(T)}{3}$.

${\rm (ⅱ)}$ $\gamma_{tI}(T)\leq \frac{2n(T)+l(T)+3s(T)-2}{3}$.

Proof. By Theorem 3.2 and Corollary 3.5, we have that $2\gamma(T)\leq \gamma_{tI}(T)\leq n(T)-\gamma(T)+s(T).$ From this previous inequality chain we deduce that $\gamma(T)\leq (n(T)+s(T))/3$, which completes the proof of (ⅰ).

Finally, we proceed to prove (ⅱ). By Corollary 3.5 and the fact that $\gamma(T)\geq (n(T)-l(T)+2)/3$ (see ^[17]), it follows that

which completes the proof.

In addition, the bound $\gamma_{tI}(T)\geq \left\lceil(2(n(T)-l(T)+3))/3 \right\rceil$ given in ^[4] can also be deduced as a consequence of the relationships $\gamma_{tI}(T)\geq 2\gamma(T)$ and $\gamma(T)\geq (n(T)-l(T)+2)/3$ and the characterization of the previous equality given by Lemańska ^[17].

Finally, we propose some open problems that arise from the results obtained in the article.

${\rm (ⅰ)}$ Characterize the trees with $\gamma_{tI}(T) = 2\gamma(T)$.

${\rm (ⅱ)}$ Characterize the trees with $\gamma_{tI}(T) = n(T)-\gamma(T)+s(T)$ or $\gamma_{\times 2}(T) = n(T)-\gamma(T)+s(T).$

${\rm (iii)}$ Characterize the trees attaining the bounds given in the inequality chain (4.1).

${\rm (iv)}$ Obtain new lower and upper bounds on the total Italian domination number of trees.

Acknowledgments

The authors would like to thank the anonymous reviewers for the careful reading of the manuscript, and for all the suggestions which contributed to improve the quality and presentation of the paper.

Conflict of interest

The authors declare no conflict of interest.