Perfect double Italian domination of a graph

Abstract

For a graph $G=(V,E)$ with $V=V(G)$ and $E=E(G)$, a perfect double Italian dominating function is a function $f:V\to \{0,1,2,3\}$ having the property that $3\le \sum _{u\in N_G[v]}f(u)\le 4$, for every vertex $v\in G$ with $f(v)\in \{0,1\}$. The weight of a perfect double Italian dominating function f is the sum $f(V)=\sum _{v\in V(G)}f(v)$ and the minimum weight of a perfect double Italian dominating function on G is the perfect double Italian domination number ${\gamma }_{dI}^p(G)$ of G. We initiate the study of perfect double Italian dominating functions. We check the ${\gamma }_{dI}^p$ of some standard graphs and evaluate with γ_dI of such graphs. The perfect double Italian dominating functions versus perfect double Roman dominating functions are perused. The NP-completeness of this parameter is verified even when it is restricted to bipartite graphs. Finally, we characterize the graphs G of order n with ${\gamma }_{dI}^p(G)\in \{3,4,5,n,2n-3,2n-4,2n-5,2n-6\}$.

Keywords:

• Double Italian domination
• perfect double Italian domination
• perfect double Roman domination
• complexity

2010 Mathematics Subject Classification:

• 05C69

1 Introduction

Throughout this paper, we suppose that, G is a simple finite graph with vertex set $V=V(G)$ and edge set $E=E(G)$. We use [23] as a reference for terminologies and notations which are not explicitly defined here. Let $G=(V,E)$ be a graph. For $u,v\in V(G)$, we use the notation $u\sim v$ to denote u and v are adjacent. The open neighborhood of a vertex $v\in V(G)$ is the set $N(v)=\{u\in$G $:u\sim v\}$. The closed neighborhood of a vertex $v\in V(G)$ is $N[v]=N(v)\cup \left\{v\right\}$. The open neighborhood of a set $S\subseteq V$ is the set $N(S)={\cup }_{v\in S}N(v)$. The closed neighborhood of a set $S\subseteq V$ is the set

$N[S]=N(S)\cup S={\cup }_{v\in S}N[v]$. Also when we write $N_S(x)$, we mean the set $\{y\in N(x):y\in S\}$. We denote the degree of v by $d_G(v)=|N(v)|$. By $\Delta =\Delta (G)$ and $\delta =\delta (G)$, we denote the maximum degree and minimum degree of a graph G, respectively. The distance between two vertices u and v is denoted by d(u, v). We write K_n, P_n and C_n for the complete graph, path and cycle of order n, respectively (see [23]).

A vertex is pendant if it is of degree one. An edge is said to be pendant if one of its vertices is a pendant vertex. For a graph G, when we use the notation G + e, we mean that e is added as an edge to the G with the end points in G. Let G be a graph with $V(G)=\{v_1,v_2,\dots v_n\}$. The Mycielski graph $\mu (G)$ of G is a simple graph with vertices $V\cup U\cup \left\{w\right\}$ where $U=\{u_1,u_2,\dots u_n\}$ is an independent set, N(w) = U and $N(u_i)\cap V=N(v_i)\cap V$ [23]. In this section we show that conjecture 3 is true for the families of Mycielski graphs.

A set $S\subseteq V$ in a graph G is called a dominating set if $N[S]=V$. The domination number $\gamma (G)$ of G is the minimum cardinality of a dominating set in G, and a dominating set of G of cardinality $\gamma (G)$ is called a γ-set of G. A dominating set S of a graph G is called a perfect dominating set if each vertex of G – S is dominated by exactly one vertex in S. The minimum cardinality of a perfect dominating set of G is the perfect domination number ${\gamma }_p(G)$. Perfect domination number and several variations on perfect dominating sets have received much attention in the literature; see some discussions in [12], or see the survey in [16].

Given a graph G and a positive integer $m\ge 2$, assume that $g:V(G)\to \{0,1,2,\dots ,m\}$ is a function, and suppose that $(V_0,V_1,V_2,\dots ,V_m)$ is the ordered partition of V induced by g, where $V_i=\{v\in V:g(v)=i\}$ for $i\in \{0,1,\dots ,m\}$. So we can write $g=(V_0,V_1,V_2,\dots ,V_m)$.

A Roman dominating function (an RDF) on G is a function $f:V\to \{0,1,2\}$ such that if f(v) = 0 for some $v\in V$, then there exists a vertex $w\in N(v)$ for which f(w) = 2. The weight of a Roman dominating function is the sum $w_f=f(V)=\sum _{v\in V(G)}f(v)$, and the minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by ${\gamma }_R(G)$ [7, 12, 21].

Already, some researchers worked on perfect Roman dominating set, for example see [8, 15, 19]. As defined in [15] a function $f=(V_0,V_1,V_2)$ is called a perfect Roman dominating function (or briefly, PRDF) if every vertex $u\in V_0$ is adjacent to exactly one vertex v for which $v\in V_2$. The minimum weight of any PRDF of G is called the perfect Roman domination number ${\gamma }_R^p(G)$ of G.

An Italian dominating function (Roman {2}-dominating function) is a function $f:V\to \{0,1,2\}$ such that for every vertex $v\in V$, with f(v) = 0, either there is at leaset one vertex $u\in N(v)$ with f(u) = 2, or there are at least two vertices $x,y\in N(v)$ with $f(x)=f(y)=1$, see [6, 14].

Recently, Haynes et al [13], introduced the concept of perfect Italian domination in graphs and trees and this concept was further discussed in [4, 22].

As defined [4, 13], a perfect Italian dominating function (PID-function) of a graph G is a function $f:V(G)\to \{0,1,2\}$ satisfying the condition that for every v in V with f(v) = 0, we have $\sum _{u\in N(v)}(f(u))=2$. The perfect Italian domination number of G denoted ${\gamma }_I^p(G)$ is the minimum weight of a PID-function of G.

Beeler et al. [5] have defined double Roman domination as follows.

A double Roman dominating function (abbreviated DRD-function) on a graph G is a function $f:V\to \{0,1,2,3\}$ such that the following conditions are met:

1. if f(v) = 0, then vertex v must have at least two neighbors in V₂ or one neighbor in V₃.

2. if f(v) = 1, then vertex v must have at least one neighbor in $V_2\cup V_3$.

The weight of a double Roman dominating function f on G is the sum $w_f=\sum _{v\in V(G)}f(v)$, and the minimum weight of w_f for every double Roman dominating function f on G is called double Roman domination number of G. We denote this number with ${\gamma }_{dR}(G)$ and a double Roman dominating function of G with weight ${\gamma }_{dR}(G)$ is called a ${\gamma }_{dR}(G)$-function of G, see also [11, 17].

The concept of perfect double Roman dominating function of a graph G, abbreviated PDRD-function, is introduced in [10]. As defined in [10], a function $f:V(G)\to \{0,1,2,3\}$ is a perfect double Roman dominating function (PDRD-function) if it is a DRD-function on G and if f(u) = 0, then u is either adjacent to exactly two vertices in V₂ and no vertex in V₃ or adjacent to exactly one vertex in V₃ and no vertex in V₂, and if f(u) = 1, then u is adjacent to exactly one vertex in V₂ and no vertex in V₃. The perfect double Roman domination number, denoted ${\gamma }_{dR}^p(G)$, is the minimum weight of a PDRD-function of G.

Recently, Mojdeh and Volkmann [18] defined double Italian (Roman {3}-)dominating functions as follows:

For a graph G, a double Italian (Roman {3}-)dominating function is a function $f:V\to \{0,1,2,3\}$ having the property that for every vertex $u\in V$, if $f(u)\in \{0,1\}$, then $\sum _{v\in N[u]}(f(v))\ge 3$. Formally, a double Italian dominating function $f:V\to \{0,1,2,3\}$ has the property that for every vertex $v\in V$, with f(v) = 0, there exist at least either three vertices in $V_1\cap N(v)$ or one vertex in $V_1\cap N(v)$ and one vertex in $(V_2\cap N(v))\cup (V_3\cap N(v))$ or two vertices in $V_2\cap N(v)$ or one vertex in $V_3\cap N(v)$ and for every vertex $v\in V$, with f(v) = 1, there exist at least either two vertices in $V_1\cap N(v)$ or one vertex in $(V_2\cup V_3)\cap N(v)$. The weight of a double Italian dominating function is the sum $w_f=f(V)=\sum _{v\in V}f(v)$, and the minimum weight of a double Italian dominating function f is the double Italian domination number, denoted by ${\gamma }_{dI}(G)$, see also [2, 3, 20].

Now we define a variant of perfect (Roman, Italian, double Roman) dominating function, namely, perfect double Italian dominating function (or perfect Roman {3}-dominating function). Hereafter we use the double Italian instead of Roman {3} and perfect double Italian instead of perfect Roman {3}. Also, by ${\gamma }_{dI}^p(G)$ of G, we mean the perfect double Italian domination number of a graph G.

Definition 1.

A perfect double Italian dominating function (abbreviated, PDIDF or PDID-function) is a function $f:V\to \{0,1,2,3\}$ having the property that,

1. for any vertex $v\in G$, if f(v) = 0, then v is either adjacent to at least 3 and at most 4 vertices in V₁ and no vertex in $V_2\cup V_3$, or is adjacent to at least 1 vertex and at most 2 vertices in V₁ and exactly one vertex in V₂ and no vertex in V₃, or is adjacent to at most one vertex in V₁ and exactly one vertex in V₃ and no vertex in V₂, or is adjacent to two vertices in V₂ and no vertex in $V_1\cup V_3$, and

2. if f(v) = 1, then v either is adjacent to at least 2 vertices and at most 3 vertices in V₁ and no vertex in $V_2\cup V_3$, or is adjacent to at most one vertex of V₁ and exactly one vertex in V₂ and no vertex in V₃, or is adjacent to exactly one vertex in V₃ and no vertex in $V_1\cup V_2$.

The weight of a perfect double Italian dominating function f is the sum $f(V)=\sum _{v\in V(G)}f(v)$ and the minimum weight of a perfect double Italian dominating function on G is the perfect double Italian domination number (abbreviated, PDIDN or PDID number) of G, denoted by ${\gamma }_{dI}^p(G)$.

We immediately have, for $v\in V_0\cup V_1$ $$3\le \sum _{u\in N_G\left[v\right]}f(u)\le 4.$$

As we remark on definition of PDIDF and definition of PDRDF, one of the differences between them is the neighborhood of any vertex in $V_0\cup V_1$. Under any PDRDF, a vertex in V₀ (V₁) is adjacent to only two vertices of V₂ or only one vertex in V₃ (only one vertex in V₂) while under any PDIDF f, a vertex v in V₀ (V₁) has the property, $3\le \sum _{u\in N_G[v]}f(u)\le 4$. In addition, for any PDRDF f on a graph G, if $3\le \sum _{u\in N_G[v]}f(u)\le 4$ for vertex $v\in V_0\cup V_1$, then f is a PDIDF on G. There are several examples of graphs G for which ${\gamma }_{dI}^p(G)<{\gamma }_{dR}^p(G)$. For instance consider cycles C_n for $n\equiv 1\text{or}5(\text{mod}6)$ ([1] and Observation 3). Also see Theorem 9 for other such examples.

We proceed as follows. In Section 2, we present some known results on the PDID number and show that ${\gamma }_{dI}(G)<{\gamma }_{dI}^p(G)$ for a family of graphs G. In Section 3, the PDID versus PDRD are studied. By patterning the paper [1] for NP-completeness, we show that PDID is NP-complete even when restricted to bipartite graphs in Section 4. Finally, we characterize the graph G of order n with ${\gamma }_{dI}^p(G)\in \{3,4,5,n,2n-3,2n-4,2n-5,2n-6\}$ in Section 5.

2 Specific values of perfect double Italian domination

In this section, we study the ${\gamma }_{dI}^p$ of some standard graph G and peruse the PDID number versus DID number. By the Definition 1, it is well known that, for any graph G ${\gamma }_{dI}(G)\le {\gamma }_{dI}^p(G)$.

We start by graph path P_n. In [18] it has been checked.

Observation 1.

([18, Observation 4]) Let $n\ge 1$. Then ${\gamma }_{dI}(P_n)=\{\begin{array}{cc}n& \text{if }n\equiv 0(\mathit{mod}3)\\ n+1& \text{otherwise }\end{array}.$

If we assign value 3 to the vertices v_i, $i\equiv 2(\text{mod}3)$ for any path P_n and assign 2 to v_n for $n\equiv 1(\text{mod}3)$, and 0 otherwise, then these assignments denote that each vertex of P_n is perfect double Italian dominated. Therefore $${\gamma }_{dI}^p(P_n)\le \{\begin{array}{cc}n& \text{if }n\equiv 0(\text{mod}3)\\ n+1& \text{otherwise }\end{array}.$$

Now from Observation 1 we have.

Corollary 2.

Let $n\ge 1$. Then ${\gamma }_{dI}^p(P_n)=\{\begin{array}{cc}n& \text{if }n\equiv 0(\mathit{mod}3)\\ n+1& \text{otherwise }\end{array}.$

Since assigning 1 to each vertex of C_n gives a ${\gamma }_{dI}^p(C_n)=n$ and using Observation 6 of [18] we observe that ${\gamma }_{dI}^p(C_n)\le {\gamma }_{dI}(C_n)$ and therefore.

Observation 3.

For a cycle C_n, ${\gamma }_{dI}^p(C_n)=n$.

Proposition 4.

For any complete bipartite graph we have.

1. ${\gamma }_{dI}^p(K_{1,n})={\gamma }_{dI}(K_{1,n})=3$,

2. ${\gamma }_{dI}^p(K_{2,n})={\gamma }_{dI}(K_{2,n})=4$ for $n\ge 2$,

3. ${\gamma }_{dI}^p(K_{3,n})={\gamma }_{dI}(K_{3,n})=5$, for $n\ge 3$,

4. ${\gamma }_{dI}^p(K_{m,n})={\gamma }_{dI}(K_{m,n})=6$ for $m,n\ge 4$.

Proof.

1. The function f devotes value 3 to the center vertex of $K_{1,n}$ and 0 otherwise, is a PDIDF of $K_{1,n}$.

2. The function f devotes value 2 to the vertices of the partite set with two vertices of $K_{2,n}$ and 0 otherwise, is a PDIDF of $K_{2,n}$.

3. The function f devotes value 1 to the vertices of the partite set with three vertices of $K_{3,n}$, value 2 to one vertex of the other partite set and 0 otherwise, is a PDIDF of $K_{3,n}$.

4. The function f devotes value 3 to one vertex of each partite set and 0 otherwise, is a PDIDF of $K_{3,n}$. Now using Proposition 8 of [18] and this fact that ${\gamma }_{dI}(G)\le {\gamma }_{dI}^p(G)$, the results are observed.□

We have similar result for complete r-partite graphs for $r\ge 3$.

Proposition 5.

Let $G=K_{n_1,n_2,\dots ,n_r}$ be the complete r-partite graph with $r\ge 3$ and $n_1\le n_2\le \cdots \le n_r$.

1. If $n_1=1$, then ${\gamma }_{dI}^p(G)=3$,

2. If $n_1=2$, then ${\gamma }_{dI}^p(G)=4$,

3. If $n_1\ge 3$ and $r\ge 4$, then ${\gamma }_{dI}^p(G)=4$,

4. If $n_1\ge 3$ and r = 3, then ${\gamma }_{dI}^p(G)=6$.

Proof.

1. The function f devotes value 3 to the vertex of the first partite set and 0 otherwise is a PDIDF of G.

2. The function f devotes value 2 to the vertices of the first partite set and 0 otherwise is a PDIDF of G.

3. The function f devotes value 1 to the one vertex of the four partite sets and 0 otherwise is a PDIDF of G.

   For checking the results in items 1–3, use Proposition 9 of [18].

4. The function f devotes value 2 to the one vertex of each partite set and 0 otherwise is a PDIDF of G.

   On the other hands we cannot assign value 2 to the one vertex of two partite sets and 1 to the one vertex of another, or 3 to the one vertex of one partite set and 2 to another partite set and 0 otherwise. Because the first assignments is not a PDIDF of G and the second assignments is not a DIDF of G. Therefore for item 4, ${\gamma }_{dI}^p\ge 6$ and the equality holds.□

In [9], it was shown that.

Proposition 6.

[9, Proposition 5.1] Let T be a tree of order n. If there exists three vertices u, v and w such that the induced subgraph $G[\{u,w,v\}]=P_3$ with $d(u,v)=2$, where w is adjacent to exactly one leaf or deg(w) = 2 and $f(u)=f(v)=3$ for every γ_dR-function and ${\gamma }_{dR}^p$-function of T, then ${\gamma }_{dR}(T)<{\gamma }_{dR}^p(T)$.

Since any PDIDF of a graph G is a DIDF of G, we deduce that ${\gamma }_{dI}(G)\le {\gamma }_{dI}^p(G)$, in particular for trees T, ${\gamma }_{dI}(T)\le {\gamma }_{dI}^p(T)$. It is easy to check that the tree T offered in Proposition 6 has the property ${\gamma }_{dI}(T)<{\gamma }_{dI}^p(T)$. As well, in what follows we show a family of trees T, and graphs G which have property that the ${\gamma }_{dI}(T)<{\gamma }_{dI}^p(T)$ and ${\gamma }_{dI}(G)<{\gamma }_{dI}^p(G)$. See Figure 1, T₁ , blue label denote the ${\gamma }_{dI}(T_1)$ and red label denote the ${\gamma }_{dI}^p(T_1)$.

Fig. 1 The trees T_i with ${\gamma }_{dI}(T_i)<{\gamma }_{dI}^p(T_i)$.

Also we have the following proposition for the relation between PDIDF and DIDF which is also right for the relation between PDRDF and DRDF.

Proposition 7.

Let T be a tree of order n. If there exists five vertices v_i, ($1\le i\le 5$) such that the induced subgraph $G[\{v_1,v_2,v_3,v_4,v_5\}]=P_5$ with $d(v_1,v_5)=4$, where v_i, ($2\le i\le 4$) is of degree 2 and $f(v_1)=f(v_5)=3$ for every γ_dI-function and ${\gamma }_{dI}^p$-function of T, then ${\gamma }_{dI}(T)<{\gamma }_{dI}^p(T)$.

Proof.

If f assigns weight 2 to v₃ and weight 0 to v₂, v₄, this is a double Italian domination but is not the case for perfect double Italian domination and any ${\gamma }_{dI}^p$-function f assigns weight $f(v_2)=0,f(v_3)=1$ and $f(v_4)=2$, or $f(v_2)=2,f(v_3)=0$ and $f(v_4)=1$, (Figure 1, T₂ ). Thus, ${\gamma }_{dI}(T)<{\gamma }_{dI}^p(T)$. See Figure 1, T₂, blue label denote the ${\gamma }_{dI}(T_2)$ and red label denote the ${\gamma }_{dI}^p(T_2)$. □

The Figure 1; trees T₁ and T₂ are examples of Propositions 6 and 7, respectively, where the blue labels denote the ${\gamma }_{dI}(T)$ and the red labels denote the ${\gamma }_{dI}^p(T)$ for $T\in \{T_1,T_2\}$.

In Figure 1, (T₁ and T₂) we show that ${\gamma }_{dI}(T_i)<{\gamma }_{dI}^p(T_i)$. Maybe finding graphs G whose double Italian domination number and perfect double Italian domination number are different is not without grace. In the Figure 2, we intend to present a construction of T₁ as an example of a graph G with this property that ${\gamma }_{dI}(G)<{\gamma }_{dI}^p(G)$ and propose its generalization as a problem.

Fig. 2 The graphs G with ${\gamma }_{dI}(G)<{\gamma }_{dI}^p(G)$.

The graph G (Figure 2(a,b)) is a Mycielski construction of T₁.

Proposition 8.

Let G be the Mycielski of T₁ ($\mu (T_1)$). Then ${\gamma }_{dI}(\mu (T_1))<{\gamma }_{dI}^p(\mu (T_1))$.

Proof.

In Figure 2(a), the assignments denote the ${\gamma }_{dI}(\mu (T_1))\le 8$. Now consider Figure 2(b) and let f be a ${\gamma }_{dI}^p(G)$ function. If $f(w_1)\ge 2$ and $f(N(w_1))=0$, then, since $G-N[w_1]=T_1$ and ${\gamma }_{dI}^p(T_1)=8$ (Figure 1, T₁), we deduce ${\gamma }_{dI}^p(G)\ge 9$. Let $f(N(w_1))\ge 1$ and $f(w_1)\ge 0$. The following must be definite.

$f(v_1)+f(w_1)+f(w_6)\ge 3,f(v_2)+f(w_1)+f(w_6)\ge 3,f(v_3)+f(w_2)+f(w_6)\ge 3,f(v_4)+f(w_2)+f(w_6)\ge 3$. The same way $f(u_1)+f(w_1)+f(w_7)\ge 3,f(u_2)+f(w_1)+f(w_7)\ge 3,f(u_3)+f(w_5)+f(w_7)\ge 3,f(u_4)+f(w_5)+f(w_7)\ge 3$. For these eight summations, the minimum values that maybe assigned, are $f(w_6)=f(w_7)=3$. In this case, for PDI dominating, we have to assign the value at least 2 to the vertices w₄ and w₅. Thus ${\gamma }_{dI}^p(G)\ge 9$. If $f(w_6)\ne 3$ or $f(w_7)\ne 3$, then the best possible are $f(w_6)=2,f(w_1)=f(w_2)=1$ and $f(w_7)+f(w_1)+f(w_3)\ge 3$, or $f(w_7)=2,f(w_1)=f(w_3)=1$ and $f(w_6)+f(w_1)+f(w_2)\ge 3$. In this case, also for PDI dominating, we have to assign the value at least 2 to the vertices w₄ or w₅. Again we have ${\gamma }_{dI}^p(G)\ge 9$. The other possible assignments trivially show that ${\gamma }_{dI}^p(G)\ge 9$. Therefore the result is observed. □

We end this section with a problem.

Problem.

For tree T supposed in Propositions 6 and 7, maybe have ${\gamma }_{dI}(\mu (T))<{\gamma }_{dI}^p(\mu (T))$.

3 PDID versus PDRD

We want to make a comparison between perfect double Italian domination and perfect double Roman domination of a graph G. From definitions of PDRD-function, PDID-function and Observation 3 and Proposition 4.7 of [4], we deduce ${\gamma }_{dI}^p(G)\le {\gamma }_{dR}^p(G)$.

In [18] authors showed that for any tree T ${\gamma }_{dI}(T)={\gamma }_{dR}(T)$ (Theorem 5 of [18]). Here we show that, it is not necessary the equality hold for ${\gamma }_{dI}^p(T)$ and ${\gamma }_{dR}^p(T)$. In addition, we show that the difference between them tends to be infinite. For this, consider the Figure 3.

Fig. 3 The graphs G with ${\gamma }_{dI}^p(T)<{\gamma }_{dR}^p(T)$.

In the figure we have three sets of vertices. The first category is pendant vertices, the second category is support vertices, and the third category is vertices that are neither leaves nor supports. In any ${\gamma }_{dR}^p$-function f of trees T in Figure 3 the vertices of the first and third categories must be assigned 2 under f, and the second category must be assigned value 0 under f. In any ${\gamma }_{dI}^p$-function, g of trees T in Figure 3, vertices of the first category should be assigned 2 under g, vertices of the second category should be assigned 0 under g and there are two cases for assigning to vertices of the third category.

• Case 1. Let T be a tree such as T₁ where the order of the third category is $m\equiv 0(\mathit{mod}3)$. In this case for the vertex v_i in the third category, we define $$g(v_i)=\{\begin{array}{cc}2& \text{if }i\equiv 1(\mathit{mod}3)ori=m-1\\ 1& \text{otherwise }\end{array}.$$

• Case 2. Let T be a tree such as T₂ or T₃ where the order of the third category is $m\cancel{\equiv }0(\mathit{mod}3)$. In this case for the vertex v_i in the third category, we define $$g(v_i)=\{\begin{array}{cc}2& \text{if }i\equiv 1(\mathit{mod}3)\\ 1& \text{otherwise }\end{array}.$$

This shows that.

Theorem 9.

For any positive integer r, there exist a tree T such that ${\gamma }_{dR}^p(T)-{\gamma }_{dI}^p(T)=r$.

Proof.

If T is a tree such as T₁ in Figure 3 where the order of the third category is $m=3k$, then ${\gamma }_{dR}^p(T)=18k$, and ${\gamma }_{dI}^p(T)=16k+1$.

If T is a tree such as T₂ in Figure 3 where the order of the third category is $m=3k+1$, then ${\gamma }_{dR}^p(T)=18k+6$, and ${\gamma }_{dI}^p(T)=16k+6$.

If T is a tree such as T₃ in Figure 3 where the order of the third category is $m=3k+2$, then ${\gamma }_{dR}^p(T)=18k+12$, and ${\gamma }_{dI}^p(T)=16k+11$.

Therefore, for even r we construct a tree such as T₂ and for odd r we construct a tree such as T₁ or T₃. □

Figure 3 denotes a family of trees T such that ${\gamma }_{dR}^p(T)>{\gamma }_{dI}^p(T)$. We can have as a problem

Problem.

Maybe characterize the trees T for which ${\gamma }_{dR}^p(T)>{\gamma }_{dI}^p(T)$?

4 Complexity and computational results

In this section, our aim is to study the complexity of the perfect double Italian domination of graphs and the following decision problem, to which we shall refer as PDIDP: In [1] Ahangar et al. showed that the double Roman domination problem is NP-complete even when restricted to bipartite and planar graphs. Here we use similar method for showing that the perfect double Italian domination problem is NP-complete even when restricted to bipartite graphs. The details of the proof due to the proof of NP-completeness of DRD problem of [1] and NP-completeness of DID problem of [18]. Consider the following decision problem.

Perfect double Italian domination problem, PDIDP.

INSTANCE: Graph $G=(V,E)$, and a positive integer $k\le \left|V\right|$.

QUESTION: Does G have a perfect double Italian domination of weight at most k?

We show that the NP-completeness results by reducing the well-known NP-complete problem,

Exact-3-Cover (X3C), to PDID.

EXACT 3-COVER ($X3C$).

INSTANCE: A finite set X with $\left|X\right|=3q$ and a collection C of 3-element subsets of X.

QUESTION: Is there a sub-collection $C\prime$ of C such that every element of X appears

in exactly one element of $C\prime$?

Theorem 10.

PDID is NP-Complete for bipartite graphs.

Proof.

It is clear that PDID Problem belongs to $\mathcal{N}\mathcal{P}$ since we can check in polynomial time that a function $f:V\to \{0,1,2,3\}$ has weight at most k and is a Perfect double Italian dominating function. Now we have to show, how to transform any instance of X3C into an instance G of PDID so that, the solution one of them is equivalent to the solution of the other one. Let $X=\{x_1,x_2,\dots ,x_{3q}\}$ and $C=\{C_1,C_2,\dots ,C_t\}$ be an arbitrary instance of X3C. For each $x_i\in X$, we build a graph H_i obtained from a path $P_9:x_{i_1}{x}_{i_2}{x}_{i_3}{x}_{i_4}{x}_{i_5}{x}_{i_6}{x}_{i_7}{x}_{i_8}{x}_{i_9}$ by adding the edge $x_{i_2}{x}_{i_9}$. For each $C_j\in C$, we build a star $K_{1,4}$ centered at a_j for which one leaf is labeled c_j. Let $Y=\{c_1,c_2,\dots ,c_t\}$. Now to obtain a graph G, we add edges $c_j{x}_{i_1}$ if $x_{i_1}\in C_j$. It is clear that G is bipartite (for example, see Figure 4). Set $k=3t+25q$. Let H be the subgraph of G induced by the union of the $V(H_i)s$. Observe that for every PDIDF f on G, $f(V(H_i))\ge 8$ to perfect double Italian dominate all vertices on each cycle $C_8=x_{i_2}{x}_{i_3}{x}_{i_4}{x}_{i_5}{x}_{i_6}{x}_{i_7}{x}_{i_8}{x}_{i_9}{x}_{i_2}$. Moreover, since H_i has a perfect double Italian domination number equal to 9, we can assume that $f(V(H_i))\le 9$. More precisely, if $f(V(H_i))=9$, then we may assume, without loss of generality, that $f(x_{i_1})=1,f(x_{i_2})=f(x_{i_4})=f(x_{i_6})=f(x_{i_8})=2$ and $f(x_{i3})=f(x_{i_5})=f(x_{i_7})=f(x_{i_9})=0$. Also, if $f(V(H_i))=8$, then clearly at least one vertex of H_i (including $x_{i_1}$) is not perfect double Italian dominated. In this case, we may assume that vertices of H_i are assigned as follows so that only $x_{i_1}$ is not Perfect double Italian dominated: $f(x_{i_2})=f(x_{i_4})=f(x_{i_6})=f(x_{i_8})=2$ and $f(x_{i_1})=f(x_{i_3})=f(x_{i_5})=f(x_{i_7})=f(x_{i_9})=0$.

Fig. 4 Bipartite graph G.

Fig. 5 The graphs G₁, G₂, and G₃.

Fig. 6 Graph G related to ${\mathcal{E}}_4$.

Fig. 7 Graphs $C^{+},C^{++},P^{+}$.

Fig. 8 Graphs $M,F,C^{+},N$.

Suppose that the instance X, C of $X3C$ has a solution $C\prime$. We construct a perfect double Italian dominating function f on G of weight k. For every C_j, assign the value 1 to c_j if $C_j\in C\prime$ and 0 if $C_j\notin C\prime$. Assign 3 to every a_j and 0 to each leaf neighbor of a_j. Finally, for every i, assign 2 to $x_{i_2},x_{i_4},x_{i_6},x_{i_8}$, and 0 to the remaining vertices of H_i. Since $C\prime$ exists, $|C\prime |=q$, the number of $c_j^{\prime }s$ with weight 1 is q, having disjoint neighborhoods in $\{x_{1_1},x_{2_1},\dots ,x_{3q_1}\}$, where every $x_{i_1}$ has one neighbors assigned 1 and one neighbor assigned 2. Hence, it is straightforward to see that f is a perfect double Italian dominating function with weight $f(V)=3t+q+24q=k$.

Conversely, let $g=(V_0,V_1,V_2,V_3)$ be a perfect double Italian dominating function of G with weight at most k. Clearly, each star needs a weight of at least 3, and so we may assume, without loss of generality, that $g(a_j)=3$ and all its leaves are assigned 0. Since $a_j\sim c_j$ in (G), it follows that each vertex c_j may be assigned the value 0. Moreover, as mentioned above, for each i, $g(V(H_i))\in \{8,9\}$. We may assume that the vertices of H_i are assigned the values given in the second paragraph depending on whether $g(V(H_i))=8$ or $g(V(H_i))=9$. Let p be the number of H_is having weight 9. Hence $g(V(H))=9p+8(3q-p)=24q+p$. Now, if $g(c_j)>0$ for some j, then c_j serves to perfect double Italian dominate some vertex $x_{r_1}$, and in that case $g(c_j)=1$ (since $g(x_{i_2})=2)$. Let y be the number of $c_j^{\prime }s$ assigned 1. Then $3t+y+24q+p\le k=3t+25q$, implies that $y+p\le q$. On the other hand, since each c_j has exactly three neighbors in $\{x_{1_1},x_{2_1},\dots ,x_{3q_1}\}$, we must have $3y\ge 3q-p$. Combining these two inequalities, we arrive at p = 0 and y = q. Consequently, $C\prime =\{C_j:g(c_j)=1\}$ is an exact cover for C. □

5 Characterization

In this section, we want to characterize the graphs whose PDID numbers are given. We bring up three categories in terms of PDID number.

1. ${\gamma }_{dI}^p(G)\in \{3,4,5\}$.

2. ${\gamma }_{dI}^p(G)=n$ where $n=|V(G)|$.

3. ${\gamma }_{dI}^p(G)\in \{2n,2n-1,2n-2,2n-3,2n-4,2n-5,2n-6\}$.

5.1 ${\gamma }_{dI}^p(G)\in \{3,4,5\}$

In [18], the characterization ${\gamma }_{dI}(G)\in \{3,4\}$ has been performed so far.

Let G be a graph of order $n\ge 2$, with ${\gamma }_{dI}(G)=3$. Then G is connected and $\Delta (G)=n-1$ ([18] Observation 7). Since any vertex of label 0 is adjacent to a vertex of wight 3, it is clear that this devoting give us a PDIDF of G of weight 3. Therefore we have.

Observation 11.

Let G be a graph of order $n\ge 2$. Then ${\gamma }_{dI}^p(G)=3$ if and only if ${\gamma }_{dI}(G)=3$.

Let G be a connected graph of order $n\ge 3$, with ${\gamma }_{dI}(G)=4$. Then Proposition 10 of [18] denotes $\Delta (G)\le n-2$ and any vertex of label 0 is adjacent to two vertices of wight 2, or at most four and at least three vertices of weight 1, and every vertex of label 1 has at most three and at least two neighborhoods of weight 1. It is obvious, this devoting presents a PDIDF of G of weight 4. Therefore we have.

Observation 12.

Let G be a connected graph of order $n\ge 3$. Then ${\gamma }_{dI}^p(G)=4$ if and only if ${\gamma }_{dI}(G)=4$.

Now we characterize graphs G for which ${\gamma }_{dI}^p(G)=5$.

For characterizing the graphs G of order $n\ge 5$ with ${\gamma }_{dI}^p(G)=5$, we construct the families of graphs as follows:

• ${\mathcal{F}}_1$. There is a path $P_3=u_1{u}_2{u}_3$ such that $G=P\cup H$, where $P\in \{P_3,P\prime =P_3-e\}$ and every vertex of H is adjacent to exactly 2 vertices of P and for P = P₃, we must have $d_G(u_2)\le n-2$.

• ${\mathcal{F}}_2$. $G=C_3\cup H$ and there exists a vertex $a\in V(H)$ such that for every $x\in N_H(a)$, x is adjacent to one or two vertices of C₃, a is not adjacent to any vertex of C₃ and for every $x\notin N_H(a)$, x is adjacent to all vertices of C₃.

• ${\mathcal{F}}_3$. $G=C_4\cup H$, where $d_G(x)\in \{d_H(x)+2,d_H(x)+3\}$ for each $x\in V(H)$ and if $A=\{x\in V(H):d_G(x)=d_H(x)+2\}$, then all vertices in A has a common neighbor in $V(C_4)$.

• ${\mathcal{F}}_4$. G contains a subgraph H of order at least two and the vertices $u_1,u_2,u_3,u_4$ such that u_is form a $K_{1,3}$ with center u₄ and there exists a vertex x in H for which $x\in N(u_i)$ for $1\le i\le 3$ and $x\notin N(u_4)$.

• ${\mathcal{F}}_5$. $G=C\cup H$, where $C\in \{C_5,C_5+e\}$ such that every vertex of H is adjacent to 3 or 4 vertices in C.

• ${\mathcal{F}}_6$. $G=(C_5+\{e,f\})\cup H$, where $\Delta (C_5+\{e,f\})=3$, each vertex of H is adjacent to exactly 3 or 4 vertices in $C_5+\{e,f\}$ and if $u\in V(C_5)$ and $d_{C_5+\{e,f\}}(u)=3$, then there exists some vertex $v\in V(H)$ such that $u\in N_G(v)\cap V(C_5)$ and $|N_G(v)\cap V(C_5)|=3$.

Theorem 13.

Let G be a connected graph of order $n\ge 3$. Then ${\gamma }_{dI}^p(G)=5$ if and only if $G\in \mathcal{F}={\cup }_{i=1}^6{\mathcal{F}}_i$.

Proof.

If $G\in {\cup }_1^5{\mathcal{F}}_i$, then it is clear that ${\gamma }_{dI}^p(G)=5$. Conversely, let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{dI}^p$-function of G. By definition, $\left|V_1\right|+2\left|V_2\right|+3\left|V_3\right|=5$. Hence $(|V_1|,|V_2|,|V_3|)\in \{(2,0,1),(1,2,0),(0,1,1),(3,1,0),(5,0,0)\}$.

0. In the case of $(|V_1|,|V_2|,|V_3|)=(2,0,1)$, there exist two vertices u₁, u₂ with assigned 1 and one vertex u₃ with assigned 3. Therefore in this case, u₃ is adjacent to every vertex of $V(G)\setminus \{u_1,u_2,u_3\}$, implying that $\Delta (G)=n-1$ and so ${\gamma }_{dI}^p(G)=3$, a contradiction to that ${\gamma }_{dI}^p(G)=5$. Similarly, if $(|V_1|,|V_2|,|V_3|)=(0,1,1)$, we also have a contradiction.

1. In the case of $(|V_1|,|V_2|,|V_3|)=(1,2,0)$, there exist two vertices u₁, u₂ with assigned 2 and one vertex u₃ with assigned 1, see Figures G₁ and G₂. Therefore, if ${\gamma }_{dI}^p(G)=5$, then $G\in {\mathcal{F}}_1$.

2. In the case of $(|V_1|,|V_2|,|V_3|)=(3,1,0)$, there exist three vertices $u_1,u_2,u_3$ with assigned 1 and one vertex u₄ with assigned 2. By the definition, it is easy to check that the induced subgraph by u_is is either $C_3\cup K_1$ or C₄, or $K_{1,3}$. If the induced subgraph by u_is is $C_3\cup K_1$, then by putting $V(K_1)=\left\{a\right\}$, we imply that $G\in {\mathcal{F}}_2$ (see Figure G₃). If the induced subgraph by u_is is C₄, then we have $G\in {\mathcal{F}}_3$. If the induced subgraph by u_is is $K_{1,3}$, then we have $G\in {\mathcal{F}}_4$.

3. For the case of $(|V_1|,|V_2|,|V_3|)=(5,0,0)$. It is straightforward that, $G\in {\mathcal{F}}_5\cup {\mathcal{F}}_6$. □

5.2 ${\gamma }_{dI}^p(G)=|V(G)|$

In this section, we investigate graphs G for which ${\gamma }_{dI}^p(G)$ is equal to the order of G. Observations 1 and 3 shows that ${\gamma }_{dI}^p(P_n)=n$ for $n\equiv 0(\mathit{mod}3)$ and ${\gamma }_{dI}^p(C_n)=n$. For this approach, we construct the following families of graphs.

• ${\mathcal{E}}_1$. G is a graph obtained from H and K, such that $G=H\cup K$, with $|V(H)|=2|V(K)|$, every vertex in H is adjacent to exactly one vertex in K and $|N_G(x)\cap V(H)|\ge 1$ for each $x\in V(K)$.

• ${\mathcal{E}}_2$. $G=H\cup \overline{K}$, where K is a complete graph, $|V(H)|=|V(K)|$, and every vertex of H is adjacent to exactly two vertices in $\overline{K}$ and $|N_G(x)\cap V(H)|\ge 1$ for any $x\in \overline{K}$.

• ${\mathcal{E}}_3$. G = C_n or $G=C_n+\{e_1,e_2,\dots ,e_k\}$ such that $\Delta (G)\le 3$ and for each u of degree three, there exists $v\in N_G(u)$ such that $d_G(v)=2$.

• ${\mathcal{E}}_4$. There exist three graphs H, C, K such that $G=H\cup C\cup K$ such that $|V(H)|=|V(C)|+2|V(K)|$ and the set of vertices H, C and K satisfy the condition (i) and exactly one of the two conditions (ii) and (iii).

1. For any $x\in H,|N_G(x)\cap V(C)|\in \{0,2\}$, and $|N_G(x)\cap V(K)|\in \{0,1\}$.

2. For any $x\in H$, if $|N_G(x)\cap V(C)|=2$, then $|N_G(x)\cap V(K)|=0$.

3. For any $x\in H$, if $|N_G(x)\cap V(C)|=0$, then $|N_G(x)\cap V(K)|=1$.

• ${\mathcal{E}}_5$. There exist two graphs H and K of orders z and 2z, respectively, where $V(H)=\{h_1,h_2,\dots ,h_z\}$, such that $G=H\cup K\cup C$, where H, K and C satisfy in the following properties:

1. Every vertex in K is adjacent to exactly one vertex in H.

2. Every vertex in H is adjacent to at least one vertex in K.

3. $K={\cup }_{i=1}^z{K}_i$ where for each $1\le i\le z,K_i=N_G(h_i)\cap V(K)$.

4. If for some i, $\left|K_i\right|\ge 3$, then there are $\left|K_i\right|-2$ indices like js, such that $\left|K_j\right|=1$.

5. For each $x\in H,|N_G(x)\cap V(C)|=0$.

6. For each $1\le i\le z,|K_i\cap N(C)|<\left|K_i\right|$.

• ${\mathcal{E}}_6$. $G=H_0\cup H_1\cup H_2$, where $|V(H_2)|=|V(H_0)|=r,H_2=\overline{K_r}$, and for $x_0\in H_0,|N(x_0)\cap H_2|=2$, for $x_1\in H_1,|N(x_1)\cap H_2|=1$. Or $H_0\cup H_2\in {\mathcal{E}}_2$ and $H_1\in {\mathcal{E}}_3$.

• ${\mathcal{E}}_7$. $G=H_0\cup H_1\cup H_2\cup H_3$ where $|V(H_0)|=|V(H_2)|+2|V(H_3)|,H_i\ne \varnothing$, and for $x\in H_0,0\le |N_G(x)\cap V(H_1)|\le 4$, or $0\le |N_G(x)\cap V(H_2)|\le 2$, or $0\le |N_G(x)\cap V(H_3)|\le 1$, and for $x\in H_1,0\le |N_G(x)\cap V(H_1)|\le 3$, or $0\le |N_G(x)\cap V(H_2\cup H_3)|\le 1$, such that:

1. For $x\in H_0$, one of the following holds:

1. If $$, then $|N_{H_2\cup H_3}(x)|=0$.

2. If $|N_G(x)\cap V(H_1)|=2$, then $|N_G(x)\cap V(H_2)|=1$ and $|N_G(x)\cap V(H_3)|=0$.

3. If $|N_G(x)\cap V(H_1)|=1$, then $|N_G(x)\cap V(H_2\cup H_3)|=1$.

4. If $|N_G(x)\cap V(H_1)|=0$, then $|N_G(x)\cap V(H_2)|\ne 1$, and exactly one of $|N_G(x)\cap V(H_2)|=0$ or $|N_G(x)\cap V(H_3)|=0$ holds.

5. If $|N_G(x)\cap V(H_1)|=0$, and $|N_G(x)\cap V(H_2)|=2$, then $|N_G(x)\cap V(H_3)|=0$.

6. If $|N_{H_1\cup H_2}(x)|=0$, then $|N_G(x)\cap V(H_3)|=1$.

1. For $x\in H_1$, one of the followings holds:

2. If $2\le |N_G(x)\cap V(H_1)|\le 3$, then $|N_G(x)\cap V(H_2\cup H_3)|=0$.

3. If $|N_G(x)\cap V(H_1)|=1$, then $|N_G(x)\cap V(H_2)|=1$ and $|N_G(x)\cap V(H_3)|=0$.

4. If $|N_G(x)\cap V(H_1)|=0$, then $|N_G(x)\cap V(H_2\cup H_3)|=1$.

Theorem 14.

Let G be a connected graph of order n. Then ${\gamma }_{dI}^p(G)=n$ if and only if $G\in {\cup }_{i=1}^7{\mathcal{E}}_i$.

Proof.

If $G\in {\cup }_{i=1}^7{\mathcal{E}}_i$, then it is easy to see that ${\gamma }_{dI}^p(G)=n$.

Conversely, let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{dI}^p$-function of G. By definition, $\left|V_1\right|+2\left|V_2\right|+3\left|V_3\right|=n$, and since $\left|V_0\right|+\left|V_1\right|+\left|V_2\right|+\left|V_3\right|=n,\left|V_0\right|=\left|V_2\right|+2\left|V_3\right|$. So, there exist the following cases.

• Case 1. $\left|V_1\right|=\left|V_2\right|=0$. So $\left|V_0\right|=2\left|V_3\right|$. Therefore, there must be existed two graphs H and K such that $G=H\cup K$, with $|V(H)|=2|V(K)|$. We assign the value 0 to the vertices of H and the value 3 to the vertices of K. Therefore, in this case, $G\in {\mathcal{E}}_1$.

• Case 2. $\left|V_1\right|=\left|V_3\right|=0$. Then $\left|V_0\right|=\left|V_2\right|$. Therefore, every vertex with value 0 is adjacent to two vertices with value 2, and the vertices with value 2 are independent. In this case, $G\in {\mathcal{E}}_2$.

• Case 3. $\left|V_0\right|=\left|V_3\right|=0$. So $\left|V_2\right|=0$. Hence all vertices are assigned with the value 1. Therefore, $G\in {\mathcal{E}}_3$.

• Case 4. $\left|V_1\right|=0$, that is $V(G)=V_0\cup V_2\cup V_3$ and $\left|V_0\right|=\left|V_2\right|+2\left|V_3\right|$. So every vertex V₀ must be adjacent to only one vertex in V₃ or adjacent to only two vertices in V₂. Let H be the induced subgraph of V₀, C be the induced subgraph of V₂, and K be the induced subgraph of V₃. Therefore, in this case, $G\in {\mathcal{E}}_4$.

• Case 5. $\left|V_2\right|=0$ and $\left|V_3\right|\ne 0$ and hence $\left|V_0\right|=2\left|V_3\right|$. Therefore each vertex of weight 0 is adjacent to only one vertex of weight 3 and each vertex of weight 3 is adjacent to at least one vertex of weight 3. If a vertex of weight 3 is adjacent to $t\ge 3$ vertices, of weight 0, then each of t – 2 other vertices of weight 3 must have only one neighbor vertex of weight 0. Any vertex of weight 1 is not adjacent to a vertex of weight 3. If $U=\{u_1,\dots ,u_r\}$ is a set of vertices of weight 0 and $U=N(x)$ where x is a vertex of weight 3 and $r\ge 2$, and if C is an induced subgraph of the vertices of weight 1, then $|U\cap N(C)|<\left|U\right|$. Therefore, in this case, $G\in {\mathcal{E}}_5$.

• Case 6. $\left|V_3\right|=0$ and $\left|V_2\right|\ne 0$ and hence $\left|V_0\right|=\left|V_2\right|$. Thus any vertex of weight 0 is adjacent to two vertices of weight 2. The vertices of of weight 2 should not be adjacent together. Every vertex of weight 1 must be adjacent to a vertex of weight 2 or adjacent together. Therefore, in this case, $G\in {\mathcal{E}}_6$.

• Case 7. $V_i\ne \varnothing$ for any $0\le i\le 3$. So every vertex in V₀ must be adjacent to only three or four vertices of V₁, or only two vertices of V₁ and one vertex of V₂, or only one vertex of V₁ and one vertex of $V_2\cup V_3$, or only two vertices of V₂, or only one vertex of V₃.

Also every vertex of V₁ must be adjacent to only two or three vertices of V₁, or only one vertex of V₁ and one vertex of V₂, or only one vertex of $V_2\cup V_3$. Therefore, $G\in {\mathcal{E}}_7$. □

5.3 ${\gamma }_{dI}^p(G)\in \{2n,2n-1,2n-2,2n-3,2n-4,2n-5,2n-6\}$

In this section, we characterize graphs G for which $2n-6\le {\gamma }_{dI}^p(G)\le 2n$ where n is the order of G. For $2n,2n-1$ and $2n-2$, the proof is straightforward and they are left.

Theorem 15.

Let G be a graph of order n. Then

1. ${\gamma }_{dI}^p(G)=2n$ if and only if $G=\overline{K_n}$.

2. ${\gamma }_{dI}^p(G)=2n-1$ if and only if $G=\overline{K_{n¯2}}\cup K_2$.

3. ${\gamma }_{dI}^p(G)=2n-2$ if and only if $G=\overline{K_{n¯4}}\cup 2K_2$ or $G=\overline{K_{n¯3}}\cup P_3$.

Theorem 16.

Let G be a graph of order n. Then ${\gamma }_{dI}^p(G)=2n-3$ if and only if one of the followings holds:

1. $G=3K_2\cup \overline{K_{n¯6}}$.

2. $G=P_3\cup \overline{K_{n¯3}}$, or $G=C_3\cup \overline{K_{n¯3}}$.

3. $G=\overline{K_{n¯2}}\cup P_4$.

Proof.

Let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{dI}^p$-function f of G with ${\gamma }_{dI}^p(G)=2n-3$. Then $\left|V_0\right|+\left|V_1\right|+\left|V_2\right|+\left|V_3\right|=n$ and $\left|V_1\right|+2\left|V_2\right|+3\left|V_3\right|=2n-3$. Therefore $2\left|V_0\right|+\left|V_1\right|-\left|V_3\right|=3$. It is well known that $\left|V_3\right|\le \left|V_0\right|$, otherwise there exists a vertex v of weight zero with $f(N_G(v))\ge 6$, and for $\left|V_0\right|\ge 4$, or $\left|V_1\right|\ge 4$ we will have $\left|V_3\right|>\left|V_0\right|$. On the other hand, if $\left|V_1\right|=3$, then we must have $\left|V_0\right|=0=\left|V_3\right|$. Now we may consider some cases.

• Case 1. $\left|V_0\right|=0=\left|V_3\right|$ and $\left|V_1\right|=3$, or $\left|V_0\right|=3=\left|V_3\right|$ and $\left|V_1\right|=0$, or $\left|V_0\right|=2=\left|V_3\right|$ and $\left|V_1\right|=1$. Then ${\gamma }_{dI}^p(G)=2n-3$ if and only if $G=3K_2\cup \overline{K_{n¯6}}$.

• Case 2. $\left|V_0\right|=2,\left|V_1\right|=0$ and $\left|V3\right|=1$. Then ${\gamma }_{dI}^p(G)=2n-3$ if and only if $G=P_3\cup \overline{K_{n¯3}}$, or $G=C_3\cup \overline{K_{n¯3}}$.

• Case 3. $\left|V_0\right|=1=\left|V_1\right|$ and $\left|V3\right|=0$. Then ${\gamma }_{dI}^p(G)=2n-3$ if and only if $G=\overline{K_{n¯2}}\cup P_4$. □

Theorem 17.

Let G be a graph of order n. Then ${\gamma }_{dI}^p(G)=2n-4$ if and only if one of the followings holds:

1. $G=\overline{K_{n¯4}}\cup C_4$ or $G=C_3\cup K_2\cup \overline{K_{n¯5}}$.

2. $G=\overline{K_{n¯5}}\cup C_3\cup K_2$, or $G=\overline{K_{n¯5}}\cup P_3\cup K_2$.

3. $G=\overline{K_{n¯5}}\cup P_5$.

4. $G=\overline{K_{n¯6}}\cup P_4\cup K_2$.

5. $G=\overline{K_{n¯8}}\cup 4K_2$.

Proof.

Let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{dI}^p$-function f of G with ${\gamma }_{dI}^p(G)=2n-4$. Then $\left|V_0\right|+\left|V_1\right|+\left|V_2\right|+\left|V_3\right|=n$ and $\left|V_1\right|+2\left|V_2\right|+3\left|V_3\right|=2n-4$. Therefore $2\left|V_0\right|+\left|V_1\right|-\left|V_3\right|=4$. It is well known that $\left|V_3\right|\le \left|V_0\right|$, and for $\left|V_0\right|\ge 5$, or $\left|V_1\right|\ge 1$ and $\left|V_0\right|\ge 4$, or $\left|V_1\right|\ge 2$, and $\left|V_0\right|\ge 3$, or $\left|V_1\right|\ge 3$, and $\left|V_0\right|\ge 2,\left|V_1\right|\ge 4$, and $\left|V_0\right|\ge 1$, we will have $\left|V_3\right|>\left|V_0\right|$. On the other hand, if $\left|V_1\right|=4$, then we must only have $\left|V_0\right|=0=\left|V_3\right|$, because the other value for $\left|V_0\right|=\left|V_3\right|$ is impossible.

Now we may consider some cases.

• Case 1. $\left|V_0\right|=0=\left|V_3\right|$ and $\left|V_1\right|=4$. Then, ${\gamma }_{dI}^p(G)=2n-4$ if and only if $G=C_3\cup K_2\cup \overline{K_{n¯5}}$, or $G=C_4\cup \overline{K_{n¯4}}$.

• Case 2. $\left|V_0\right|=3,\left|V_3\right|=2$ and $\left|V_1\right|=0$, or $\left|V_0\right|=2,\left|V_3\right|=1$ and $\left|V_1\right|=1$. ${\gamma }_{dI}^p(G)=2n-4$ if and only if $G=P_3\cup K_2\cup \overline{K_{n¯5}}$, or $G=C_3\cup P_2\cup \overline{K_{n¯5}}$.

• Case 3. $\left|V_0\right|=2,\left|V_1\right|=0=\left|V_3\right|=0$. Then ${\gamma }_{dI}^p(G)=2n-4$ if and only if $G=P_5\cup \overline{K_{n¯5}}$.

• Case 4. $\left|V_0\right|=1,\left|V_1\right|=2$ and $\left|V_3\right|=0$. Then ${\gamma }_{dI}^p(G)=2n-4$ if and only if $G=P_4\cup K_2\cup \overline{K_{n¯6}}$.

• Case 5. $\left|V_0\right|=4,\left|V_1\right|=0$ and $\left|V_3\right|=4$ or $\left|V_0\right|=\left|V_3\right|=3$ and $\left|V_1\right|=1$. Then ${\gamma }_{dI}^p(G)=2n-4$ if and only if $G=4K_2\cup \overline{K_{n¯8}}$. □

Theorem 18.

Let G be a graph of order n. Then ${\gamma }_{dI}^p=2n-5$ if and only if one of the followings holds:

1. $G=\overline{K_{n¯4}}\cup H$, where $H\in \{K_{1,3},K_{1,3}+e,K_4-e,K_4\}$.

2. $G=\overline{K_{n¯5}}\cup H$Z $G=\overline{K_{n¯5}}\cup H$, where $H\in \{C_4^{+},C_3^{++}\}$ where $C_4^{+}$ and $C_3^{++}$ are the bellow graphs.

3. $G=\overline{K_{n¯7}}\cup H$, where $H\in \{P_3\cup 2K_2,C_3\cup 2K_2,P_5\cup K_2,P^{+}\cup K_2\}$ where P⁺ is the bellow graph.

4. $G=\overline{K_{n¯10}}\cup H$, where $H=5K_2$.

Proof.

Let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{dI}^p$-function f of G with ${\gamma }_{dI}^p(G)=2n-5$. Then $\left|V_0\right|+\left|V_1\right|+\left|V_2\right|+\left|V_3\right|=n$ and $\left|V_1\right|+2\left|V_2\right|+3\left|V_3\right|=2n-5$. Therefore $2\left|V_0\right|+\left|V_1\right|-\left|V_3\right|=5$. It is well known that $\left|V_3\right|\le \left|V_0\right|$, and for $\left|V_0\right|\ge 6$, or $\left|V_1\right|\ge 1$ and $\left|V_0\right|\ge 5$, or $\left|V_1\right|\ge 2$, and $\left|V_0\right|\ge 4$, or $\left|V_1\right|\ge 3$, and $\left|V_0\right|\ge 3$, or $\left|V_1\right|\ge 4$, and $\left|V_0\right|\ge 2$, or $\left|V_1\right|\ge 5$, and $\left|V_0\right|\ge 1$, we will have $\left|V_3\right|>\left|V_0\right|$. On the other hand, if $\left|V_1\right|=5$, then we must only have $\left|V_0\right|=0=\left|V_3\right|$, because of the other value for $\left|V_0\right|=\left|V_3\right|$ is impossible. Now we may consider some cases.

• Case 1. $\left|V_0\right|=3,\left|V_3\right|=1$ and $\left|V_1\right|=0$, or $\left|V_0\right|=1,\left|V_1\right|=3$ and $\left|V_3\right|=0$, or $\left|V_0\right|=2,\left|V_1\right|=1,\left|V_2\right|\ge 1$, and $\left|V_3\right|=0$. Then ${\gamma }_{dI}^p=2n-5$ if and only if $G=\overline{K_{n¯4}}\cup H$, where $H\in \{K_{1,3},K_{1,3}+e,K_4-e,K_4\}$.

• Case 2. $\left|V_0\right|=2,\left|V_1\right|=1,\left|V_3\right|=0$ and $\left|V_2\right|\ge 2$. Then, ${\gamma }_{dI}^p=2n-5$ if and only if $G=\overline{K_{n¯5}}\cup H$, where $H\in \{C_4^{+},C_3^{++}\}$.

• Case 3. $\left|V_0\right|=4,\left|V_3\right|=3$ and $\left|V_1\right|=0$, or $\left|V_0\right|=1,\left|V_1\right|=3,\left|V_3\right|=0$ and $\left|V_2\right|\ge 3$, or $\left|V_0\right|=3,\left|V_1\right|=1,\left|V_3\right|=2$ and $\left|V_2\right|\ge 1$, or $\left|V_0\right|=2,\left|V_1\right|=2,\left|V_3\right|=1$ and $\left|V_2\right|\ge 2$. Then, ${\gamma }_{dI}^p=2n-5$ if and only if $G=\overline{K_{n¯7}}\cup H$, where $H\in \{P_3\cup 2K_2,C_3\cup 2K_2,P_5\cup K_2,P^{+}\cup K_2\}$.

• Case 4. $\left|V_0\right|=5,\left|V_3\right|=5$ and $\left|V_1\right|=0$, or $\left|V_0\right|=4,\left|V_1\right|=1,\left|V_3\right|=4$ and $\left|V_2\right|\ge 1$, or $\left|V_0\right|=3,\left|V_1\right|=2,\left|V_3\right|=3$ and $\left|V_2\right|\ge 2$, or $\left|V_0\right|=2,\left|V_1\right|=3,\left|V_3\right|=2$ and $\left|V_2\right|\ge 3$, or $\left|V_0\right|=1,\left|V_1\right|=4,\left|V_3\right|=1$ and $\left|V_2\right|\ge 4$, or $\left|V_0\right|=0=\left|V_3\right|,\left|V_1\right|=5$ and $\left|V_2\right|\ge 5$. Then, ${\gamma }_{dI}^p=2n-5$ if and only if $G=\overline{K_{n¯10}}\cup H$, where $H=5K_2$. □

Theorem 19.

Let G be a graph of order n. Then ${\gamma }_{dI}^p=2n-6$ if and only if one of the followings holds:

1. $G=\overline{K_{n¯6}}\cup H$, where $H\in \{C_6,C_6+e,C_4^{++},2P_3,P_3\cup C_3,F,2C_3,K_{1,3}\cup K_2,C_3^{+}\cup K_2,K_4-e\cup K_2,K_4\cup K_2,N\}$ or $G=\overline{K_{n¯5}}\cup (\overline{K_2}\vee K)$ where K is a graph of order 3 and size at most 1.

2. $G=\overline{K_{n¯7}}\cup H$, where $H\in \{P_7,M\}$.

3. $G=\overline{K_{n¯9}}\cup H$, where $H\in \{P_3\cup 3K_2,C_3\cup 3K_2\}$.

4. $G=\overline{K_{n¯12}}\cup 6K_2$.

Proof.

Let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{dI}^p$-function f of G with ${\gamma }_{dI}^p(G)=2n-6$. Then $2\left|V_0\right|+\left|V_1\right|-\left|V_3\right|=6$. It is well known that $\left|V_3\right|\le \left|V_0\right|$, and for $\left|V_0\right|\ge 7$, or $\left|V_1\right|\ge 1$ and $\left|V_0\right|\ge 6$, or $\left|V_1\right|\ge 2$, and $\left|V_0\right|\ge 5$, or $\left|V_1\right|\ge 3$, and $\left|V_0\right|\ge 4$, or $\left|V_1\right|\ge 4$, and $\left|V_0\right|\ge 3$, or $\left|V_1\right|\ge 5$, and $\left|V_0\right|\ge 2$, or $\left|V_1\right|\ge 6$, and $\left|V_0\right|\ge 1$, we will have $\left|V_3\right|>\left|V_0\right|$. On the other hand, if $\left|V_1\right|=6$, then we must only have $\left|V_0\right|=0=\left|V_3\right|$, because of the other value for $\left|V_0\right|=\left|V_3\right|$ is impossible. Now we may consider some cases.

• Case 1. $\left|V_0\right|=3,\left|V_3\right|=0,\left|V_1\right|=0$ and $\left|V_2\right|\le 3$, or $\left|V_0\right|=4,\left|V_3\right|=2$ and $\left|V_1\right|=0$, or $\left|V_0\right|=1,\left|V_1\right|=4,\left|V_3\right|=0$, and $\left|V_2\right|\ge 1$, or $\left|V_0\right|=2,\left|V_1\right|=2,\left|V_3\right|=0$ and $\left|V_2\right|\ge 2$. Then, ${\gamma }_{dI}^p=2n-6$ if and only if $G=\overline{K_{n¯6}}\cup H$, where $H\in \{C_6,C_6+e,C_4^{++},2P_3,P_3\cup C_3,F,2C_3,K_{1,3}\cup K_2,C_3^{+}\cup K_2,K_4-e\cup K_2,K_4\cup K_2,N\}$ or $G=\overline{K_{n¯5}}\cup (\overline{K_2}\vee K)$ where K is a graph of order 3 and size at most 1.

• Case 2. $\left|V_0\right|=3,\left|V_3\right|=0,\left|V_1\right|=0$ and $\left|V_2\right|\ge 4$. Then, ${\gamma }_{dI}^p=2n-6$ if and only if $G=\overline{K_{n¯7}}\cup H$, where $H\in \{P_7,M\}$.

• Case 3. $\left|V_0\right|=5,\left|V_3\right|=4,\left|V_1\right|=0$, or $\left|V_0\right|=2,\left|V_3\right|=1$ and $\left|V_1\right|=3$, or $\left|V_0\right|=3,\left|V_1\right|=2,\left|V_3\right|=2$, and $\left|V_2\right|\ge 2$, or $\left|V_0\right|=4,\left|V_1\right|=1,\left|V_3\right|=3$, and $\left|V_2\right|\ge 1$. Then, ${\gamma }_{dI}^p=2n-6$ if and only if $G=\overline{K_{n¯9}}\cup H$, where $H\in \{P_3\cup 3K_2,C_3\cup 3K_2\}$.

• Case 4. $\left|V_0\right|=6,\left|V_3\right|=6,\left|V_1\right|=0$, or $\left|V_0\right|=2,\left|V_1\right|=4,\left|V_3\right|=2$ and $\left|V_2\right|=4$, or $\left|V_0\right|=3,\left|V_1\right|=3,\left|V_3\right|=3$, and $\left|V_2\right|\ge 3$, or $\left|V_0\right|=4,\left|V_1\right|=2,\left|V_3\right|=4$, and $\left|V_2\right|\ge 2$, or $\left|V_0\right|=5,\left|V_1\right|=1,\left|V_3\right|=5$, and $\left|V_2\right|\ge 1$. Then, ${\gamma }_{dI}^p=2n-6$ if and only if $G=\overline{K_{n¯12}}\cup 6K_2$. □

We end the paper with the following problem.

Problem.

Characterize the graph G for which, ${\gamma }_{dI}^p(G)\in \left\{\right|V(G)|-1,|V(G)|-2\}$.

Acknowledgments

The second author (Parvin Jalilolghadr) has been supported by “the University of Mazandaran,” when she was visiting the University of Mazandaran as a Post Doctoral Researcher. We are grateful to the anonymous referee for their useful comments on this paper that improved its presentation.