Noor A'lawiah Abd Aziz^a , Hailiza Kamarulhaili^a , Farzaneh Azvin^b , Nader Jafari Rad^∗b

^aSchool of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM Penang, Malaysia ^bDepartment of Mathematics, Shahed University, Tehran, Iran

nooralawiah@gmail.com, hailiza@usm.my, azvin.f4@gmail.com, n.jafarirad@gmail.com

An outer-independent Italian dominating function (OIIDF) on a graph G is a function f : V (G) −→ {0, 1, 2} such that every vertex v ∈ V (G) with f(v) = 0 has at least two neighbors assigned 1 under f or one neighbor w with f(w) = 2, and the set {u ∈ V (G)|f(u) = 0} is independent. An outer-independent double Italian dominating function (OIDIDF) on a graph G is a function f : V (G) −→ {0, 1, 2, 3} such that if f(v) ∈ {0, 1} for a vertex v ∈ V (G), then P u∈N[v] f(u) ≥ 3 and the set {u ∈ V (G)|f(u) = 0} is independent. The weight of an OIIDF (respectively, OIDIDF) f is the value w(f) = P v∈V (G) f(v). The minimum weight of an OIIDF (respectively, OIDIDF) on a graph G is called the outer-independent Italian (respectively, outer-independent double Italian) domination number of G. We characterize all trees T with outer-independent double Italian domination number twice the outer-independent Italian domination number. We also present lower bounds on the outer-independent double Italian domination number of a connected graph G in terms of the order, minimum and maximum degrees.

Keywords: (Italian, double Italian, outer-independent Italian) domination, outer-independent double Italian domination Mathematics Subject Classification : 05C69

DOI: 10.5614/ejgta.2022.10.2.2

Received: 23 April 2021, Revised: 16 April 2022, Accepted: 19 April 2022.

^∗ corresponding author

1. Introduction

We consider simple connected graphs G with vertex set V=V(G) and edge set E=E(G). The order of G is n(G)=|V|. The open neighborhood of a vertex v is the set \(N(v)=\{u\in V(G)\mid uv\in E\}\) and its closed neighborhood is the set \(N[v]=N(v)\cup\{v\}\). The degree of vertex \(v\in V\) is \(\deg(v)=d(v)=|N(v)|\). The maximum degree and minimum degree among the vertices of G are denoted by \(\Delta=\Delta(G)\) and \(\delta=\delta(G)\), respectively. A leaf is a vertex of degree one, and its neighbor is called a support vertex. A strong support vertex is a support vertex adjacent to more than one leaf. For a subset D of vertices of G, we denote by G[D] the subgraph of G induced by G0. A subset G1 of G2 is a dominating set in G3 if G3 if G4 is a subgraph of a graph G5 is called independent if no pair of vertices of G5 are adjacent. If G5 is a subgraph of a graph G6 and G6 is a function defined on G6, then we denote by G6 is a subgraph of a graph G6 and G6 is a function defined on G6, then we denote by G6 is a function of G6 in G6. For other notations and terminology not given here we refer to G6.

Cockayne et al. [12] introduced the concept of Roman domination in graphs, and since then many generalizations and related variations have been considered by researchers, see [7, 8, 9, 10, 11, 16, 19]. A variation of Roman domination, namely, double Roman domination is introduced by Beeler et al. [4]. A generalization of double Roman domination, namely Italian domination, is introduced by Chellali et al. in [6] and further studied in [15] and [17]. An Italian dominating function (IDF) on a graph G is a function \(f:V(G) \longrightarrow \{0,1,2\}\) such that every vertex \(v \in V(G)\) with f(v)=0 has at least two neighbors assigned 1 under f or one neighbor w with f(w)=2. The weight of an IDF is the value \(w(f)=\sum_{u\in V(G)}f(u)\). The minimum weight of an IDF on a graph G is called the Italian domination number and denoted by \(\gamma_I(G)\). For an IDF f on G, let \(V_i^f=\{v\in V(G):f(v)=i\}\), for i=0,1,2. We can equivalently write \(f=(V_0^f,V_1^f,V_2^f)\) (or simply \(f=(V_0,V_1,V_2)\)).

Fan et al. [13] initiated the study of outer independent Italian domination in graphs. An outer independent Italian dominating function (OIIDF) on a graph G is an IDF on G that \(V_0^f\) is an independent set. Mojdeh and Volkmann [18] considered an extension of Italian domination as follows. For a graph G, a double Italian dominating function (DIDF) is a function \(f:V\longrightarrow \{0,1,2,3\}\) having the property for which every vertex \(u\in V\), if \(f(u)\in \{0,1\}\), then \(f(N[u])\geq 3\). The weight of a DIDF f is the sum \(w(f)=f(V)=\sum_{v\in V}f(v)\), and the minimum weight of a DIDF in a graph G is the double Italian domination number, denoted by \(\gamma_{\{R3\}}(G)\), or \(\gamma_{dI}(G)\) for convenience. Abdollahzadeh Ahangar et al. [1] studied outer independent double Roman domination. An outer independent double Roman dominating function (OIDRDF) on G is an DRDF of G for which \(V_0^f\) is an independent set.

Azvin et al. [3] (see also Volkmann [20]) considered those double Italian dominating functions f such that \(\{v \in V(G) \mid f(v) = 0\}\) is an independent set. An outer independent double Italian dominating function (OIDIDF) of graph G is a DIDF \(f:V(G)\longrightarrow \{0,1,2,3\}\) for which \(V_0^f\) is independent. The outer independent double Italian domination number denoted by \(\gamma_{oidI}(G)\) is the minimum weight of an OIDIDF on G. An OIDIDF on graph G with weight of \(\gamma_{oidI}(G)\) is denoted by \(\gamma_{oidI}(G)\)-function. Benatallah [5] studied outer independent double Italian domination number and presented the following bounds on the outer independent double Italian domination number.

Theorem 1.1 ([5]). For every graph G, \(\gamma_{oiI}(G) \leq \gamma_{oidI}(G) \leq 2\gamma_{oiI}(G)\) and these bounds are sharp.

In this paper we continue the study of the outer independent double Italian domination number of a graph. We characterize all trees T achieving equality in both bounds given in Theorem 1.1. We also prove two lower bounds on the outer independent double Italian domination number of a graph.

2. Trees T with \[\gamma_{oidI}(T)=2\gamma_{oiI}(T)\] or \(\gamma_{oidI}(T)=\gamma_{oiI}(T)+1\)

We aim to characterize trees achieving the equality in each of the lower or upper bounds given in Theorem 1.1. We begin with the following result.

Observation 2.1. If \[\gamma_{oil}(G) = \gamma_{oidl}(G)\] for a graph \(G\), then \(\delta(G) \geq 2\).

Proof. Suppose that γoiI (T) = γoidI (T). Let f = (V0, V1, V2, V3) be a γoidI (T)-function. If |V3| ̸= 0 then re-assigning 2 to any vertex of V³ and 1 to any vertex of V² produces an OIIDF of T of weight less than γoiI (T), a contradiction. Thus |V3| = 0. Similarly, |V2| = 0. Thus each vertex of V⁰ is adjacent to at least three vertices of V¹ and each vertex of V¹ is adjacent to at least two vertices of V1. Consequently, δ(T) ≥ 2.

As the above observation shows, no tree achieves equality for the lower bound of Theorem 1.1. We will improve the lower bound of Theorem 1.1 for trees.

Proposition 2.1. For any tree T of order n ≥ 2, γoidI (T) ≥ γoiI (T) + 1, with equality holds if and only if T is a star.

Proof. Let f = (V0, V1, V2, V3) be a γoidI (T)-function. If |V3| ̸= 0 and |V2| ̸= 0 then re-assigning 2 to any vertex of V³ and 1 to any vertex of V² produces an OIIDF of T of weight γoidI (T) − 2, implying that γoidI (T) ≥ γoiI (T) + 2. Similarly, γoidI (T) ≥ γoiI (T) + 2 if |V3| ≥ 2 or |V2| ≥ 2. Thus we may assume that (|V3|, |V2|) ∈ {(0, 1),(1, 0)}. If (|V3|, |V2|) = (0, 1), then re-assigning 1 to the vertex of V² produces an OIIDF of G of weight γoidI (T) − 1, implying that γoidI (T) ≥ γoiI (T) + 1, and if (|V3|, |V2|) = (1, 0), then re-assigning 2 to the vertex of V³ produces an OIIDF of G of weight γoidI (T) − 1, implying that γoidI (T) ≥ γoiI (T) + 1.

Now assume that γoidI (T) = γoiI (T) + 1. Let f = (V0, V1, V2, V3) be a γoidI (T)-function. Following the above argument, we obtain that(|V3|, |V2|) ∈ {(0, 1),(1, 0)}. Suppose that(|V3|, |V2|) = (0, 1). Let V² = {y}. Since f is a γoidI (T)-function and T has at least two leaves, for any leaf x ̸= y we have f(x) = 1 and x ∈ N(y). Since any vertex x ̸= y lies on a path from y to a leaf of T, we deduce that any vertex x ̸= y is a leaf. Consequently, T is a star centered at y. If deg(y) ≥ 2, then re-assigning 3 to y and 0 to any leaf produces an OIDIDF of T of weight less than γoidI (T), a contradiction. Thus T is star of order 2. Next assume that |V3| = 1 and |V2| = 0. Let V³ = {y}. Clearly, for any leaf x, f(x) = 0, and x is adjacent to y, since f is a γoidI (T)-function. Consequently, T is a star centered at y. The converse is obvious.

We next aim to characterize trees achieving the equality in the upper bound of Theorem 1.1. The following lemma has an important role in the rest of this section.

Lemma 2.1. If T is a tree for which \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T)\) and \(f = (V_0, V_1, V_2)\) is a \(\gamma_{oiI}(T)\)-function, then:

• (1) \(V_2 = \emptyset\) and \(V_1\) is an independent set.
• (2) T does not have any strong support vertex.
• (3) All leaves of T belong to the same partite set of T, namely \(X_{L(T)}\).
• (4) The distance between any pair of vertices in \(X_{L(T)}\) is even.
• (5) There exists a \(\gamma_{oidI}(T)\)-function g for which \(V_1^g \cup V_3^g = \emptyset\).

Proof. Assume that \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T)\). Let \(f = (V_0, V_1, V_2)\) be a \(\gamma_{oiI}(T)\)-function.

• (1) As it is shown in the proof of Theorem 1.1, re-assigning 2 to every vertex of \(V_1\) and 3 to every vertex of \(V_2\) produces an OIDIDF for T implying that \(\gamma_{oidI}(T) \leq 2|V_1| + 3|V_2| \leq 2|V_1| + 4|V_2| = 2\gamma_{oiI}(T) = \gamma_{oidI}(T)\) which implies that \(V_2 = \emptyset\). If there are two adjacent vertices u and v in \(V_1\), then the function g defined by g(u) = 1 and g(x) = 2f(x) for every \(x \in V(T) \{u\}\) is an OIDIDF, and so \(\gamma_{oidI}(T) \leqslant w(g) < 2w(f) = 2\gamma_{oiI}(T)\), a contradiction. Thus \(V_1\) is an independent set.
• (2) By (1), \(V_2 = \emptyset\) and both \(V_0\) and \(V_1\) are independent sets. Assume that T has a strong support vertex u. Then f(u) = 0 and f(x) = 1 for every leaf neighbor of u. Then the function g defined by g(u) = 3, g(t) = 0 for every leaf-neighbor of u, and g(x) = 2f(x) for any other vertex is an OIDIDF. Let A be the set of all leaf-neighbors of u. Then \(|A| \geqslant 2\), since u is a strong support vertex. Thus

\[\gamma_{oidI}(T) \leqslant w(g) = 3 + 2(|V_1 - A|) \leqslant 3 + 2|V_1| - 4 \leqslant 2|V_1| - 1 < 2|V_1| = 2\gamma_{oiI}(T),\]

a contradiction. Consequently, T does not have any strong support vertex.

• (3) Since \(V_2 = \emptyset\) and both \(V_0\) and \(V_1\) are independent sets, it follows that \(V_0\) and \(V_1\) are partite sets of T. Since f(x) = 1 for every leaf x, we find that all leaves belong to \(V_1\).
• (4) Let \(X_{L(T)}\) be the partite set of T containing all leaves. Let x,y be two vertices in \(X_{L(T)}\), and let \(P: x_0x_1....x_ky\) be the shortest path between x and y, where \(x_0=x\). Then clearly \(f(x)=f(y)=f(x_{2i})=1\) for \(i\leq \lfloor\frac{k}{2}\rfloor\), and f(u)=0 for any other vertex of P. Since \(V_0\) is an independent set, we conclude that k is odd. Consequently, d(x,y) is even.
• (5) In view of the proof of (1), we have \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T) = 2|V_1|\). It is now easy to see that \(g = (V_0^g, V_1^g, V_2^g, V_3^g) = (V_0, \emptyset, V_1, \emptyset)\) is a \(\gamma_{oidI}(T)\)-function for which \(V_1^g \cup V_3^g = \emptyset\).

According to Lemma 2.1, for every tree T with \(\gamma_{oidI}(T)=2\gamma_{oiI}(T)\), we denote by \(X_{L(T)}\) the partite set containing all leaves of T. Now we define the family \(\mathcal T\) of trees as follows. Let \(\mathcal T\) be the family of trees T that can be obtained from a sequence \(T_1,\ldots,T_i\) \((i\geq 1)\) of trees such that \(T_1\) is a path \(P_5\) and if \(i\geq 2\), then \(T_{i+1}\) can be obtained, recursively, from \(T_i\) by the following operation.

Operation \(\mathcal{O}\): Let \(u \in X_{L(T_i)}\). Then \(T_{i+1}\) is obtained from \(T_i\) by joining u to a leaf of a path \(P_2\).

Lemma 2.2. If \(\gamma_{oidI}(T_i) = 2\gamma_{oiI}(T_i)\) and \(T_{i+1}\) is obtained from \(T_i\) by Operation \(\mathcal{O}\), then \(\gamma_{oidI}(T_{i+1}) = 2\gamma_{oiI}(T_{i+1})\).

Proof. Let \(v \in X_{L(T_i)}\) and suppose \(T_{i+1}\) is obtained from \(T_i\) by joining v to the leaf y of a \(P_2\)-path \(P_2: yz\) according to Operation \(\mathcal{O}\). We first show that \(\gamma_{oil}(T_{i+1}) = \gamma_{oil}(T_i) + 1\). Let \(f = (V_0, V_1, V_2)\)

be a \(\gamma_{oiI}(T_i)\)-function. According to Lemma 2.1 (1), \(V_2=\emptyset\) and \(V_1\) is an independent set. If u is a leaf in \(X_{L(T_i)}\), then f(u)=1. Since d(u,v) is even, we find that f(v)=1. Then assigning 0 to y and 1 to z produces an OIIDF for \(T_{i+1}\) implying that \(\gamma_{oiI}(T_{i+1}) \leq w(f) + 1 = \gamma_{oiI}(T_i) + 1\). On the other hand, let g be a \(\gamma_{oiI}(T_{i+1})\)-function. Clearly, \(g(v)+g(z)+g(y)\geqslant 2\). We may assume that g(z)=1, g(y)=0 and \(g(v)\geqslant 1\). Therefore \(\gamma_{oiI}(T_i)\leq w(g|_{T_i})\leqslant w(g)-1=\gamma_{oiI}(T_{i+1})-1\). Consequently, \(\gamma_{oiI}(T_{i+1})=\gamma_{oiI}(T_i)+1\).

We next prove that \(\gamma_{oidI}(T_{i+1})=2\gamma_{oiI}(T_{i+1})\). First we note that according to Proposition 1.1, \(\gamma_{oidI}(T_{i+1})\leqslant 2\gamma_{oiI}(T_{i+1})\). Conversely let \(f^*\) be a \(\gamma_{oidI}(T_{i+1})\)-function. Clearly \(f^*(y)+f^*(z)\in\{2,3\}\). If \(f^*(y)+f^*(z)=2\), then \(f^*(y)=0\) and \(f^*(z)=2\), and so \(f^*|_{T_i}\) is an OIDIDF on \(T_i\) and so \(\gamma_{oidI}(T_i)\leqslant w(f^*)-2=\gamma_{oidI}(T_{i+1})-2\). This implies that

\[\gamma_{oidI}(T_{i+1}) \geqslant \gamma_{oidI}(T_i) + 2 = 2\gamma_{oiI}(T_i) + 2 = 2(\gamma_{oiI}(T_i) + 1) = 2\gamma_{oiI}(T_{i+1})\]

as desired. Thus we assume that \(f^*(y) + f^*(z) = 3\). Without loss of generality, we may assume that \(f^*(y) = 3\) and \(f^*(z) = 0\). Then \(f^*(v) < 2\), since otherwise we can replace \(f^*(y)\) by 0 and \(f^*(z)\) by 2 to obtain an OIDIDF on \(T_{i+1}\) with weight less than \(w(f^*)\) which is a contradiction. If \(f^*(v) = 1\), then we define a function \(g^*\) by \(g^*(v) = g^*(z) = 2\), \(g^*(y) = 0\) and \(g^*(t) = f^*(t)\) otherwise. Then \(w(g^*) = w(f^*)\) and \(g^* \mid_{T_i}\) is an OIDIDF on \(T_i\). Then \(\gamma_{oidI}(T_i) \leqslant w(g^* \mid_{T_i}) = w(g^*) - 2\) and so \(\gamma_{oidI}(T_{i+1}) \geqslant \gamma_{oidI}(T_i) + 2 = 2\gamma_{oiI}(T_i) + 2 = 2(\gamma_{oiI}(T_i) + 1) = 2\gamma_{oiI}(T_{i+1})\). Thus assume that \(f^*(v) = 0\). Note that \(f^*(t) \ge 1\) for \(t \in N(v)\). If \(|N(v) - \{y\}| \ge 3\), then \(f^*|_{T_i}\) is an OIDIDF on \(T_i\) and so \(\gamma_{oidI}(T_i) \leq w(f^*|_{T_i}) = w(f^*) - 3 < w(f^*) - 2 = \gamma_{oidI}(T_{i+1})\) and we obtain the result as before. If \(|N(v) - \{y\}| = 2\), then we may assume that \(f^*(y) = 1\) and \(f^*(z) = 2\) and define the function f' by f'(v) = 1, f'(z) = 2 and f'(y) = 0. Then \(f'|_{T_i}\) is an OIDIDF on \(T_i\) and, as before, we find that \(\gamma_{oidI}(T_{i+1}) \ge 2\gamma_{oiI}(T_{i+1})\). Therefore assume that \(|N(v) - \{y\}| = 1\). Let \(N(v) - \{y\} = 1\)\(\{w\}\). If \(f^*(w) \ge 2\), then \(f'|_{T_i}\), where f' is described above, is an OIDIDF on \(T_i\), and as before the result follows. Thus assume that \(f^*(w) = 1\). Then \(h|_{T_i}\), where h is defined by h(v) = 2 and \(h(t) = f^*(t)\) otherwise, is an OIDIDF on \(T_i\). Let \(N(w) = \{v, w_1, w_2 \dots w_k\}\), where \(k \geq 1\). Let \(g_1\) be a \(\gamma_{oidI}(T)\)-function on \(T_i\) satisfying Lemma 2.1 (5). Then \(w(g_1) = 2\gamma_{oiI}(T_i)\), \(g_1(w) = 0\) and \(g_1(v) = g_1(w_i) = 2\) for i = 1, 2, ..., k. Assume that there is an integer \(j \in \{1, 2, ..., k\}\) such that \(w(h \mid_{T_{w_i}}) \ge w(g_1 \mid_{T_{w_i}})\). Then we change h(x) by \(g_1(x)\) for each \(x \in V(T_{w_i})\) and define the function \(h^*\) by \(h^*(w) = 2, h^*(w_i) = h^*(v) = 1, h^*(x) = g_1(x)\) for \(x \in V(T_{w_i}) - \{w_i\}\)and \(h^*(t) = h(t)\) otherwise. Since \(d(v, w_i) = 2\) and \(v \in X_{L(T_i)}\), \(h^*\) is an OIDIDF on \(T_i\) and so \(\gamma_{oidI}(T_i) \leq w(h^*) \leq w(h) - 1 = w(f^*) - 2\). Therefore \(\gamma_{oidI}(T_{i+1}) \geq \gamma_{oidI}(T_i) + 2\), as desired. Then we assume that \(w(h \mid_{T_{w_i}}) \leq w(g_1 \mid_{T_{w_i}}) - 1\), for every i = 1, ..., k. We now have the following.

\[\gamma_{oidI}(T_i) \leqslant h(v) + h(w) + \sum_{i=1}^k h(T_{w_i}) \leqslant 2 + 1 + \sum_{i=1}^k g_1(T_{w_i}) - k = 2\gamma_{oiI}(T_i) + 1 - k.\]

If \(k \geqslant 2\), then \(\gamma_{oidI}(T_i) < 2\gamma_{oiI}(T_i)\), a contradiction. Thus k=1. Then \(\deg(w)=2\). Observe that \(f^*(w_1)=2\), since \(f^*\) is an OIDIDF on \(T_{i+1}\). Let \(f_1\) be a function defined by \(f_1(w)=f_1(y)=0\), \(f_1(v)=f_1(z)=2\) and \(f_1(t)=f^*(t)\) otherwise. Then \(w(f_1)=w(f^*)\) and \(f_1\mid_{T_i}\) is an OIDIDF on \(T_i\). Then \(\gamma_{oidI}(T_i)\leqslant w(f_1\mid_{T_i})=\gamma_{oidI}(T_{i+1})-2\) and so

\[\gamma_{oidI}(T_{i+1}) \geqslant \gamma_{oidI}(T_i) + 2 = 2\gamma_{oiI}(T_i) + 2 = 2(\gamma_{oiI}(T_i) + 1) = 2\gamma_{oiI}(T_{i+1})\]

as desired.

We are now ready to characterize trees with outer independent double Italian domination number twice the outer independent Italian domination number.

Theorem 2.1. For a tree T of order \(n \geq 5\), \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T)\) if and only if \(T \in \mathcal{T}\).

Proof. First we show that for every tree T of the family \(\mathcal{T}\), \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T)\). We proceed by induction on the order \(n \geqslant 5\) of a tree \(T \in \mathcal{T}\). Clearly \(6 = \gamma_{oidI}(P_5) = 2\gamma_{oiI}(P_5) = 2(3)\). This establishes the base step. For the inductive hypothesis, assume that for every tree T' of order n', \((5 \leqslant n' < n)\) that belongs to the family \(\mathcal{T}\), we have \(\gamma_{oidI}(T') = 2\gamma_{oiI}(T')\). Let T be a tree of order n that belongs to the family \(\mathcal{T}\). Then T is obtained from a sequence \(T_1, \ldots, T_i\) \((i \geq 1)\) of trees such that \(T_1\) is a path \(P_5\) and if \(i \geq 2\), then \(T_{i+1}\) can be obtained, recursively, from \(T_i\) by Operation \(\mathcal{O}\). Then by the inductive hypothesis and Lemma 2.2 we obtain that \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T)\).

Conversely, assume that T is a tree of order \(n \geqslant 5\) with \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T)\). We show that \(T \in \mathcal{T}\). We proceed by induction on the order \(n \geqslant 5\). We first note that if diam(T) = 2, then T is a star and clearly \(\gamma_{oidI}(T) = 3\), \(\gamma_{oiI}(T) = 2\) and \(\gamma_{oidI}(T) \neq 2\gamma_{oiI}(T)\). If diam(T) = 3, then T is a double star in which \(\gamma_{oidI}(T) \in \{5,6\}\), \(\gamma_{oiI}(T) \in \{3,4\}\) and \(\gamma_{oidI}(T) \neq 2\gamma_{oiI}(T)\). Therefore we assume that \(diam(T) \geqslant 4\) and so \(n \geqslant 5\). If n = 5, then \(T \cong P_5 \in \mathcal{T}\). This establishes the base step of the induction. For the induction hypothesis assume that every tree T' of order n' (\(1 \le n' < n\)) with \(\gamma_{oidI}(T') = 2\gamma_{oiI}(T')\) belongs to the family \(\mathcal{T}\). Let I be a tree of order I with I and root I at I and I with I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and I and

Let \(T' = T - \{x_d, x_{d+1}\}\). We first show that \(\gamma_{oiI}(T) = \gamma_{oiI}(T') + 1\). Observe that \(f \mid_{T'}\) is an OIIDF on T'. Thus \(\gamma_{oiI}(T') \leqslant \gamma_{oiI}(T) - 1\). Assume that \(f' = (V'_0, V'_1, V'_2)\) is a \(\gamma_{oiI}(T')\)-function. If \(f'(x_{d-1}) \geqslant 1\), then the function g defined by \(g(x_d) = 0\), \(g(x_{d+1}) = 1\) and g(t) = f'(t) otherwise, is an OIIDF on T and so \(\gamma_{oiI}(T) \leqslant \gamma_{oiI}(T') + 1\). Thus we assume that \(f'(x_{d-1}) = 0\). We consider the following cases.

Case 1. \(\deg(x_{d-1}) \geqslant 3\). Since \(x_{d-1}\) does not have any leaf neighbor, we may assume that \(x_{d-1}\) has a child \(u \neq x_d\) which is a support vertex. By Lemma 2.1 \(\deg(u) = 2\). Let w be the child of u. Then f'(u) + f'(w) = 2. Then we replace \(f'(x_{d-1})\) and f'(w) by 1 and f'(u) by 0 to obtain a \(\gamma_{oiI}(T')\)-function f'' with \(f''(x_{d-1}) \geq 1\). Then, as before, the function g defined by \(g(x_d) = 0\), \(g(x_{d+1}) = 1\) and g(t) = f''(t) otherwise, is an OIIDF on T and so \(\gamma_{oiI}(T) \leqslant \gamma_{oiI}(T') + 1\), as desired.

Case 2. \(\deg(x_{d-1})=2\). Observe that \(f'(x_{d-2})=2\). Suppose that \(x_{d-2}\) has a leaf neighbor v. Then \(f(x_{d-2})=0\) and f(v)=1. Also \(x_{d-3}\) doesn't have a leaf neighbor, since \(d(x_{d-3},x_{d+1})\) is even. Now we define the function \(f_1\) by \(f_1(x_{d-2})=3\), \(f_1(v)=0\), \(f_1(x_{d-1})=f_1(x_{d-3})=1\) and \(f_1(t)=2f(t)\) otherwise. Then \(f_1\) is an OIDIDF on T and so \(\gamma_{oidI}(T)\leqslant w(f_1)=2w(f)-1\leqslant 2\gamma_{oiI}(T)\), a contradiction. Thus \(x_{d-2}\) does not have a leaf neighbor, and so every child of \(x_{d-2}\) with value 0 (if any), is adjacent to at least one other vertex with value at least 1. Then we change \(f'(x_{d-2})\) and \(f'(x_{d-1})\) to 1 to obtain a \(\gamma_{oiI}(T')\)-function f'' with \(f''(x_{d-1}) \ge 1\). Then the function

g defined by \(g(x_d)=0, g(x_{d+1})=1\) and g(t)=f''(t) otherwise, is an OIIDF on T and so \(\gamma_{oil}(T)\leqslant \gamma_{oil}(T')+1\), as desired.

We conclude that \(\gamma_{oiI}(T) = \gamma_{oiI}(T') + 1\). Thus \(\gamma_{oidI}(T) = 2\gamma_{oiI}(T) = 2(\gamma_{oiI}(T') + 1)\). Then \(\gamma_{oidI}(T) - 2 = 2\gamma_{oiI}(T')\).

We next show that \(\gamma_{oidI}(T') = \gamma_{oidI}(T) - 2\). Assume that g is a \(\gamma_{oidI}(T')\)-function. If \(g(x_{d-1}) \ge 1\)1, then we set \(g(x_d) = 0\) and \(g(x_{d+1}) = 2\) to extend g to an OIDIDF on T. Therefore \(\gamma_{oidI}(T) \leqslant\)\(\gamma_{oidI}(T') + 2\). Assume that \(g(x_{d-1}) = 0\). If \(\deg_T(x_{d-1}) = 2\), then \(g(x_{d-2}) = 3\) and \(g(x_{d-3}) + 3\)\(g(x_{d-4}) \ge 1\). Note that \(diam(T') \ge 4\), since \(\gamma_{oidI}(T') = 2\gamma_{oiI}(T')\). Since \(deg(x_{d-2}) = 2\), we may change \(g(x_{d-2})\) to 2, and set \(g(x_{d-1}) = 1\), \(g(x_d) = 0\) and \(g(x_{d+1}) = 2\) to extend g to an OIDIDF on T and as before find that \(\gamma_{oidI}(T) \leq \gamma_{oidI}(T') + 2\). Thus assume that \(\deg_T(x_{d-1}) \geq 3\). Since \(x_{d-1}\) does not have a leaf neighbor, it has a child y of degree 2. Let z be the child of y. Then g(y) + g(z) = 3. Now we change \(g(x_{d-1})\) to 1, g(y) to 0 and g(z) to 2, and as before obtain that \(\gamma_{oidI}(T) \leqslant \gamma_{oidI}(T') + 2\). We conclude that \(\gamma_{oidI}(T) \leqslant \gamma_{oidI}(T') + 2\). Next we show that \(\gamma_{oidI}(T) \geqslant \gamma_{oidI}(T') + 2\). Assume that h is a \(\gamma_{oidI}(T)\)-function. If \(h(x_{d-1}) \geqslant 2\), then \(h(x_{d+1}) + h(x_d) = 2\) and \(h|_{V(T')}\) is an OIDIDF on T', implying that \(\gamma_{oidI}(T') \leqslant \gamma_{oidI}(T) - 2\). Assume that \(h(x_{d-1}) = 1\). If \(\sum_{(v \in N[x_{d-1}] - x_d)} h(v) \geqslant 3\), then we may assume that \(h(x_d) = 0\) and \(h(x_{d+1}) = 2\), in which the result follows as before. Thus assume that \(\sum_{(v \in N[x_{d-1}] - x_d)} h(v) < 3\). Then \(h(x_d) + h(x_{d+1}) = 3\) and we may assume that \(h(x_{d+1}) = h(x_{d-1}) = 2\) and \(g(x_d) = 0\) in which the result follows as before. We now assume that \(h(x_{d-1}) = 0\). If \(\deg(x_{d-1}) \ge 3\), then \(x_{d-1}\) has a child y of degree two. Assume that z is the child of y. Since \(h(x_{d-1}) = 0\), we have \(h(t) \ge 1\) for every vertex \(t \in N(x_{d-1})\). Furthermore, \(h(x_{d+1}) + h(x_d) = h(y) + h(z) = 3\). Let h'be a function defined by \(h'(x_{d-1}) = h'(y) = 1\), \(h'(x_d) = 0\), \(h'(z) = h'(x_d) = 2\) and h'(t) = h(t)otherwise. Then \(h'|_{T'}\) is an OIDIDF on T' and so \(\gamma_{oidI}(T') \leq w(h') - 2 = w(h) - 2\) as required. Thus assume that \(deg(x_{d-1}) = 2\). If \(h(x_{d-2}) \ge 2\), then we change \(h(x_{d-1})\) to 1, \(h(x_d)\) to 0 and \(h(x_{d+1})\) to 2, and as before we find that \(\gamma_{oidI}(T') \leq \gamma_{oidI}(T) - 2\). It remains to assume that \(h(x_{d-2}) = 1\). Then \(h(x_{d-3}) \ge 2\), since \(\deg(x_{d-2}) = 2\). Now we change \(h(x_{d+1})\) and \(h(x_{d-1})\) to 2 and \(h(x_d)\) and \(h(x_{d-2})\) to 0 to obtain h'. Then \(h'|_{T'}\) is an OIDIDF on T' and the result is obtained as before. Hence, \(\gamma_{oidI}(T') = \gamma_{oidI}(T) - 2 = 2\gamma_{oiI}(T')\). We deduce \(T' \in \mathcal{T}\) by the induction hypothesis. Since \(f(x_{d-1}) = 1\), we have \(x_{d-1} \in X_{L(T)}\) and so T is formed by Operation \(\mathcal{O}\) on T'.

3. New lower bounds

In this section we prove two new lower bounds on the outer independent double Italian domination number.

Theorem 3.1. For every graph G of order n with minimum degree \(\delta = \delta(G) > 0\) and maximum degree \(\Delta = \Delta(G)\), \(\gamma_{oidI}(G) \geqslant \lfloor \frac{n\delta}{\delta + \Delta} \rfloor + 1\) and this bound is sharp.

Proof. Let G be a graph of order n with minimum degree \(\delta > 0\), and \(f = (V_0, V_1, V_2, V_3)\) be a \(\gamma_{oidI}(G)\)-function. Let m be the number of edges having one end point in \(V_0\) and the other end point in \(V_1 \cup V_2 \cup V_3\). We then have \(m \geq \delta |V_0|\), since \(V_0\) is independent and \(f(N(u)) \geq 3\) for each vertex \(u \in V_0\). On the other hand each vertex in \(V_1 \cup V_2 \cup V_3\) has at most \(\Delta\) neighbors in \(V_0\). Thus,

\(m \le \Delta(|V_1| + |V_2| + |V_3|)\), and so \(\delta(n - |V_1| - |V_2| - |V_3|) \le \Delta(|V_1| + |V_2| + |V_3|)\) which implies that \(\delta n \le (\Delta + \delta)(|V_1| + |V_2| + |V_3|)\). Therefore,

\[\frac{\delta n}{\Delta + \delta} \leqslant |V_1| + |V_2| + |V_3| = \gamma_{oidI}(G) - |V_2| - 2|V_3|.\]

If \(V_2 \cup V_3 \neq \emptyset\), then \(\gamma_{oidI}(G) \geqslant \frac{n\delta}{\Delta + \delta} + |V_2| + 2|V_3| \geqslant \frac{n\delta}{\Delta + \delta} + 1\), as desired. Thus assume that \(V_2 \cup V_3 = \emptyset\). Then each vertex in \(V_1\) is adjacent to at least two vertices in \(V_1\) and each vertex in \(V_0\) is adjacent to at least three vertices in \(V_1\). Then if \(|V_0| > 0\), then \(\Delta \geq 3\) while if \(|V_0| = 0\) then \(\Delta \geq 2\). Furthermore, counting the number of edges having one end point in \(V_0\) and the other end point in \(V_1\) implies that \(\delta |V_0| \leqslant (\Delta - 2)|V_1|\). Since \(n = |V_0| + |V_1|\), we find that \(\delta (n - |V_1|) \leqslant (\Delta - 2)|V_1|\). This implies that \(\gamma_{oidI}(G) = |V_1| \geq \frac{\delta n}{\Delta + \delta - 2} > \frac{\delta n}{\Delta + \delta}\). Since \(\gamma_{oidI}(G)\) is an integer we deduce that \(\gamma_{oidI}(G) \geqslant \lfloor \frac{n\delta}{\delta + \Delta} \rfloor + 1\). To see the sharpness, for each integer \(n \geq 3\), let \(G_n\) be a graph obtained from a cycle \(C_n\) by adding 2n new vertices and joining each new vertex to all vertices of \(C_n\). Note that \(|V(G_n)| = 3n\), \(\delta(G_n) = n\), \(\Delta(G_n) = 2n + 2\) and \(\gamma_{oidI}(G_n) = n = \lfloor \frac{3n^2}{3n+2} \rfloor + 1\).

We now introduce a family of graphs as follows. Let \(\mathcal G\) be the class of all graphs G such that \(G \in \mathcal G\) if and only if G is obtained from a graph H of order at least three and minimum degree at least two by adding at least \(|V(H)| - \delta(H)\) new vertices and joining each new vertex to all vertices of H.

Proposition 3.1. If G is a graph of order \(n \geq 1\) with minimum degree \(\delta\), \(\gamma_{oidI}(G) \geq \delta\), with equality holds if and only if \(G \in \mathcal{G}\).

Proof. The result is obvious if \(\delta \leq 2\). Thus assume that \(\delta \geq 3\). Let \(f = (V_0, V_1, V_2, V_3)\) be a \(\gamma_{oidI}(G)\)-function. If \(V_0 = \emptyset\), then \(\gamma_{oidI}(G) \geq n \geq \delta + 1\), since \(\delta \leq n - 1\). Thus assume that \(V_0 \neq \emptyset\). Let \(x \in V_0\). Therefore \(N(x) \subseteq V_1 \cup V_2 \cup V_3\), since \(V_0\) is an independent set. Also \(|N(x)| \geq \delta\). Note that

\[\gamma_{oidI}(G) = |V_1| + 2|V_2| + 3|V_3| = (\sum_{i=1}^{3} |V_i|) + |V_2| + 2|V_3|.\]

If \((V_2 \cup V_3) \neq \emptyset\), then \(\gamma_{oidI}(G) \geq \left(\sum_{i=1}^3 |V_i|\right) + 1 \geq \deg(x) + 1 \geq \delta + 1\). Thus assume that \(V_2 \cup V_3 = \emptyset\). Then \(\gamma_{oidI}(G) = |V_1|\). Since \(V_0\) is an independent set, we find that \(\gamma_{oidI}(G) = |V_1| \geq \delta\).

We next prove the equality part. Assume that \(\gamma_{oidI}(G) = \delta\). Clearly \(\gamma_{oidI}(G) \geq 2\). It is easy to see that \(\gamma_{oidI}(G) = 2\) if and only if \(G = K_1\). Since \(K_1\) has minimum degree 0, from \(\gamma_{oidI}(G) = \delta\) we obtain that \(\delta \geq 3\). Let \(f = (V_0, V_1, V_2, V_3)\) be a \(\gamma_{oidI}(G)\)-function. Following the above argument for the first part of the proof, we obtain that \(V_2 \cup V_3 = \emptyset\) and \(\gamma_{oidI}(G) = |V_1| = \delta\). Let \(H = G[V_1]\). Since \(V_0\) is independent and \(|V_1| = \delta\), every vertex of \(V_0\) is adjacent to all vertices of \(V_0\). Since any vertex of \(V_0\) is adjacent to at least two other vertices of \(V_0\), we obtain that \(V_0\) has minimum degree at least 2. Suppose that \(|V_0| < |V(H)| - \delta(H)\). Let \(V \in V_0\) be a vertex with \(\deg_H(V) = \delta(H)\). Then

\[\deg_G(v) = \deg_H(v) + |V_0| < |V(H)| = \delta(G).\]

This is a contradiction. Thus |V0| ≥ |V (H)| − δ(H). We conclude that G ∈ G.

Conversely assume that G ∈ G. Thus G is obtained from a graph H of order m ≥ 3 with V (H) = {y1, ..., ym} and δ(H) ≥ 2 by adding t ≥ m − δ(H) new vertices x1, ..., x^t , and adding edges xiy^j , for i = 1, ..., t and j = 1, ...., m. Note that degG(xi) = m for i = 1, ..., t, and degG(y^j ) = degH(y^j )+t ≥ δ(H)+t ≥ m for j = 1, ...., m. Thus δ(G) = m. Then γoidI (G) ≥ m by the first part of the proposition. Now let g be a function on G defined by g(y^j ) = 1 for each j = 1, ..., m and g(xi) = 0 for each xⁱ , i = 1, ..., t. Then g is an OIDIDF for G, implying that γoidI (G) ≤ m. Consequently, γoidI (G) = m = δ(G).

References

• [1] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Outer independent double Roman domination, Appl. Math. Comput. 364 (2020), ID: 124617.
• [2] F. Azvin and N. Jafari Rad, Bounds on the double Italian domination number of a graph, Discuss. Math. Graph Theory (to appear), doi:10.7151/dmgt.2330.
• [3] F. Azvin, N. Jafari Rad, and L. Volkmann, Bounds on the outer-independent double Italian domination number, Comm. Combin. Optim. 6 (2021), 123–136.
• [4] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
• [5] M. Benatallah, Outer-independent double Italian domination in graphs, Manuscript (2021).
• [6] M. Chellali, T. Haynes, S.T. Hedetniemi, and A. McRae, Roman domination, Discrete Appl. Math. 204 (2016), 22–28.
• [7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Eds. (Springer, 2020) 365–409. doi:10.1007/978-3-030–51117-3-11
• [8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, In: Structures of Domination in Graphs, Eds. T.W. Haynes, S.T. Hedetniemi and M.A. Henning, (Springer, 2021).
• [9] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), 966–984.
• [10] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. (to appear).
• [11] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, The Roman domatic problem in graphs and digraphs: A Survey, Discuss. Math. Graph Theory (2020), doi:10.7151/dmgt.2313.

• [12] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), 11–22.
• [13] W. Fan, A. Ye, F. Miao, Z. Shao, V. Samodivkin, and S.M. Sheikholeslami, Outerindependent Italian domination in graphs, IEEE Access 7 (2019), 22756–22762.
• [14] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York (1998).
• [15] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017), 557–564.
• [16] N. Jafari Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5(1) (2017), 1–6.
• [17] W. Klostermyer and G. MacGillivray, Roman, Italian, and 2-domination, J. Combin. Math. Combin. Comput. 108 (2019), 125–146.
• [18] D.A. Mojdeh and L. Volkmann, Roman {3}–domination (double Italian domination), Discrete Appl. Math. 283 (2020), 555–564.
• [19] A. Poureidi, Total Roman domination for proper interval graphs, Electron. J. Graph Theory Appl. 8(2) (2020), 401–413.
• [20] L. Volkmann, Remarks on the outer-independent double Italian domination number, Opuscula Math. 41(2) (2021), 259–268.