Signed double Italian domination

1.   Introduction

All graphs $G = (V, E)$ in this paper are finite, simple, and undirected. Two vertices, $u, v\in V$, are adjacent if $uv\in E$. We say $u$ is a neighbor of $v$ if $u$ and $v$ are adjacent. We denote the set of all neighbors of $v$ by $N(v)$ and the set $N(v) \cup \{v\}$ by $N[v]$. The degree of a vertex $v$ is ${\rm{d}}(v): = |N(v)|$. The maximum degree of $G$ is $\Delta(G): = \max\{{\rm{d}}(v)|v\in V\}$ and the minimum degree of $G$ is $\delta(G): = \min\{{\rm{d}}(v)|v\in V\}$. The notation $P_n$ denotes a path of order $n$, and the length of a path is the number of edges in it. The distance between two vertices $u$ and $v$ in a connected graph $G$, denoted by ${\rm{dist}}_{G}(u, v)$, is the length of a shortest path between $u$ and $v$ in $G$. The graph diameter is defined as ${\rm{diam}}(G): = \max\{{\rm{dist}}_{G}(x, y)|(x, y)\in V\times V\}$. A vertex $u$ with ${\rm{d}}(u) = 1$ is called a leaf, and any neighbor of a leaf is called a support vertex. We denote the set of leaves in $G$ by L(G) and the set of support vertices in $G$ by S(G). A vertex $v$ is called a strong support vertex if $v\in S(G)$ and $|N(v)\cap L(G)|\ge 2$, and $v$ is called a weak support vertex if $v\in S(G)$ and $|N(v)\cap L(G)| = 1$. An edge $e\in E$ is a pendant edge if it has an endpoint in $L(G)$. A tree with exactly two non-leaf vertices, $u$ and $v$, is called a double star and it is denoted by $DS_{s, t},$ where $s = {\rm{d}}(u)$ and $t = {\rm{d}}(v)$. We denote the set of integers $\{1, \cdots, n\}$ by $[n]$. If $k$ is a positive integer less than $n$, then $[n]\setminus[k]: = \{k+1, \cdots, n\}$. A decision problem is an NP problem if it can be solved in polynomial time by a non-deterministic machine.

Let $G$ be a graph and let $f$ be a function $f:V\longrightarrow A$, where $A$ is a finite subset of $\mathbb{Z}$. The weight of $f$, denoted by $w(f)$, is the sum $\sum_{v\in V}f(v)$. If $H\subseteq V,$ we denote the sum $\sum_{v\in H}f(v)$ by $f(H)$. Every function $f$ can be represented by the partition $(V_{i}^{f}|i\in A)$ of $V$, where $V_{i} = \{v\in V|f(v) = i\}.$ Sometimes, we write $V_{i}$ instead of $V_{i}^{f}$ if $f$ is known from the context.

A function $f$ from $V$ to $\{0, 1, 2\}$ is a Roman dominating function on $G$ if every vertex in $V_{0}^{f}$ is adjacent to at least one vertex in $V_{2}^{f}$. The Roman domination number of $G$, denoted by $\gamma_{R}(G)$, is the minimum weight of a Roman dominating function on $G$.

Roman domination was sparked by defensive actions taken to safeguard the Roman Empire. Every city was to have a maximum of two legions stationed there, according to a decree made by Constantine the Great, who was born in 272 and died in 337 BCE. Additionally, if a city does not have a legion, it must be near a city with two legions; in the event that the city without a legion was under attack, the city with two legions may dispatch a legion to defend it. Roman dominion was considered a mathematical notion by Stewart ^[1], ReVelle and Rosing ^[2,3] and was later developed by Cockayne et al. ^[4]. Clearly, the defense strategy would be insufficient to safeguard the empire if two attacks occurred simultaneously. This increased the necessity for a more effective defensive strategy and inspired scholars to develop and examine several Roman domination variations. Since then, more than a hundred studies on Roman dominance and its variations have been published. Italian domination ^[5], double Roman domination ^[6], signed Roman domination ^[7] and signed Italian domination ^[8] are a few examples of Roman domination variants. We refer the readers to ^{[9,10,11,12,13,14]} for recent work in Roman domination variants.

Chellali et al. ^[5] relaxed the conditions of Roman domination and introduced Italian domination. A function $f:V\longrightarrow\{0, 1, 2\}$ is an Italian dominating function on $G$, denoted by IDF, if every vertex in $V_{0}^{f}$ is adjacent to at least one vertex in $V_{2}^{f}$ or at least two vertices in $V_{1}^{f}$. The Italian domination number of $G$ is $\gamma_{I}(G): = \min \{ w(f)|\text{ }f\text{ is an IDF on }G \}$.

A function $f:V\longrightarrow\{-1, 1, 2, 3\}$ is a signed double Roman dominating function on $G$, denoted by SDRDF, if (ⅰ) for all $v\in V$, $\sum_{z\in N[v]}f(z)\ge1$; (ⅱ) every vertex in $V_{-1}^{f}$ is adjacent to at least one vertex in $V_{3}^{f}$ or adjacent to at least two vertices in $V_{2}^{f}$ and (ⅲ) every vertex in $V_{1}^{f}$ is adjacent to at least one vertex in $V_{2}^{f}\cup V_{3}^{f}$. The signed double Roman domination number of $G$, denoted by $\gamma_{sdR}(G)$, is the minimum weight of an SDRDF on $G$. Signed double Roman domination was first introduced in ^[15]. In a signed double Roman domination model, a vertex with label negative one represents a location with an auxiliary cohort. The idea of this model comes from the era of Constantine Ⅱ, when small sizes of non-Roman citizen troops were formed (the size was about $10%$ of a legion). Constantine Ⅱ reduced the number of legions by stationing those troops in some locations and requiring that the number of troops in a location and its surrounding was less than the number of legions.

In this paper, we relax the conditions of signed double Roman domination and introduce signed double Italian domination (SDID). Our motivation is to reduce the cost while still protecting the empire.

Definition 1. Let $G = (V, E)$ be a graph. A function $f:V\longrightarrow\{-1, 1, 2, 3\}$ is called a signed double Italian dominating function (SDIDF) on $G$ if (i) $\sum_{u\in N[v]}f(u)\ge1$ for every $v\in V$; (ii) for every vertex $v$ with $f(v) = -1$, there exists $A\subseteq N(v)$ such that $\sum_{u\in A}f(u)\ge3$ and (iii) for every vertex $v$ with $f(v) = 1$, there exists $A\subseteq N(v)$ such that $\sum_{u\in A}f(u)\ge2$. The signed double Italian domination number of $G$, denoted by $\gamma_{sdI}(G)$, is the minimum weight of a SDIDF on $G$. A SDIDF on $G$ with minimum weight is called a $\gamma_{sdI}(G)$-function.

It is obvious that every SDRDF on $G$ is a SDIDF, so we have the following proposition.

Proposition 1. Let $G$ be a graph, then $\gamma_{sdI}(G)\le\gamma_{sdR}(G)$.

In the following proposition, we give examples of trees $T$ for which $\gamma_{sdI}(T)\neq\gamma_{sdR}(T).$

Proposition 2. There exist infinitely many trees $T$ for which $\gamma_{sdI}(T) < \gamma_{sdR}(T)$.

Proof. Let $k$ be a positive integer. Let $T_{4k}$ be the tree obtained from the star graph $K_{1, 4k}$ by subdividing every edge once. Denote the vertex in the center by $c$. Let the set of vertices with degree two be $S: = \{v_{1}, v_{2}, \cdots v_{4k}\}$, and let the set of leaves be $L: = \{u_{1}, u_{2}, \cdots u_{4k}\}$. Fix the notations so that $v_{l}u_{l}\in E(T_{4k})$. We show that $\gamma_{sdI}(T_{4k})\le5k+1$, while $\gamma_{sdR}(T_{4k}) > 5k+1$. Define an SDIDF $f$ on $T_{4k}$ as follows. Set $f(c) = 1$, set $f(v_{l}) = -1$ and $f(u_{l}) = 2$ for every $l\in[3k]$, and set $f(v_{l}) = 3$ and $f(u_{l}) = -1$ for every $l\in[4k]\backslash[3k]$. As $f$ is an SDIDF with $w(f) = 5k+1$, then $\gamma_{sdI}(T_{4k})\le5k+1$.

Assume that $T_{4k}$ admits an SDRDF $g$ with $w(g)\le5k+1$. Observe that for every $l\in[4k],$ $\sum_{v\in N[u_{l}]}g(v) = g(u_{l})+g(v_{l})\ge1$. As $w(g)\le5k+1$, there exists $l\in[4k]$ such that $g(u_{l})+g(v_{l}) = 1$. We must have $g(u_{l}) = 2$ and $g(v_{l}) = -1$, so $g(c)\in\{2, 3\}.$ Let $a: = |\{l\in[4k]|g(u_{l})+g(v_{l}) > 1\}|$, so $|\{l\in[4k]|g(u_{l})+g(v_{l}) = 1\}| = 4k-a$. If $a\ge k$, then

a contradiction. Thus, $a\le k-1$. Now,

a contradiction. Thus, $\gamma_{sdR}(T_{4k}) > 5k+1$ as desired. □

Proposition 3. Let $G$ be a connected graph of order $n\ge2$, then $\gamma_{sdI}(G)\le n$.

Proof. If $n = 2$, then $G = P_{2}$ and the statement is clear. Assume that $n > 2$. If $\delta(G)\ge2$, we can assign value one for all $v\in V$. This gives an SDIDF $f$ on $G$ with $w(f) = n$. So, we may assume that $\delta(G) = 1$. Define an SDIDF $g$ on $G$ as follows. Assign value one to every vertex $v\in V(G)\setminus{(S(G)\cup L(G))}$. For every $v\in S(G)$, assign value three to $v$, assign value negative one to one of its leaves, and assign value one to the remaining leaves. Clearly, $w(g) = n$, and, thus, $\gamma_{sdI}(G)\le n$. □

Let $G$ be a connected graph of order $n\ge2$. Let

$A = \{v|v\text{ be a strong support vertex in }G\}$,

$B = \{v\in A| |N(v)\cap L(G)|\text{ be odd}\}$,

$C = \{v|v\text{ be a leaf adjacent to a strong support vertex}\}$.

Proposition 4. Let $G$ be a connected graph of order $n > 2$ and $G\ne K_{1, n-1}$, then $\gamma_{sdI}(G)\le n-(|B|+|C|)$.

Proof. Define an SDIDF $f$ on $G$ as follows. Set $f(v) = 1$ for all $v\in V(G)\setminus(S(G)\cup L(G))$. Let $v\in S(G)$ and $N(v)\cap L(G) = \{v_{1}, \cdots, v_{k}\}$, $k\ge1$. Set $f(v) = 3,$ $f(v_{1}) = -1$; if they exist, set $f(v_{2}) = f(v_{3}) = -1$, set $f(v_{j}) = 1$ if $j$ is even and $j\ne2$ and set $f(v_{j}) = -1$ if $j$ is odd. Do this for every support vertex $v$. As $G\ne K_{1, n-1}$, every $v\in S(G)$ has a neighbor in $V(G)\setminus L(G)$ and every non-leaf vertex is assigned a positive value; thus, $f(N[v])\ge1$. The other conditions of the SDIDF are clearly satisfied. Therefore, $\gamma_{sdI}(G)\le w(f)\le n-(|B|+|C|)$ as desired. □

2.   Complexity

In this section, we prove that the decision problem associated with SDID is NP-complete for bipartite and chordal graphs.

Define the following problem.

SDID

Instance: Graph $G$ and an integer $k\le|V|.$

Question: Does $G$ have an SDIDF of weight at most $k$?

Our reduction is from the following known NP-complete problem.

EXACT COVER BY $3$-SETS-$3$ (X3C3)

Instance: A set $X$ of size $3q$ and a collection $C = \{C_{1}, \cdots, C_{3q}\}$ of three-element subsets of $X$ such that every element $x_{i}\in X$ is in exactly three elements of $C$.

Question: Does $C$ contain an exact cover of $X$, i.e., does $C$ contain a sub-collection $C'$ such that every element $x_{i}\in X$ is in exactly one element of $C'$?

Hickey et al. ^[16] proved that X3C3 is NP-complete.

We then transform every instance of X3C3 to an instance of SDID, such that the first instance has a solution if, and only if, the second instance has a solution.

Theorem 1. SDID is NP-complete for bipartite graphs and chordal graphs.

Proof. SDID is a member of NP, as we can check in polynomial time if a function $f:$$V\longrightarrow\{-1, 1, 2, 3\}$ is an SDIDF and $w(f)\le k$. Let $X = \{x_{1}, \cdots, x_{3q}\}$ and $C = \{C_{1}, \cdots, C_{3q}\}$ be an instance of X3C3. We construct an instance of SDID. For every $i\in[3q]$, let $x_{i}$ be the center of the star graph $K_{1, 6}$. For every $j\in[3q]$, let $a_{j}$ be the center of the star graph $K_{1, 4}$, and let $c_{j}$ be one of its leaves. Finally, add the set of edges $x_{i}c_{j}$ if, and only if, $x_{i}\in C_{j}$. Call the resulting graph $G_{1}$. Let $G_{2}$ be the graph obtained from $G_{1}$ by adding the edges $c_{i}c_{j}$, where $i, j\in[3q]$ and $i\ne j$ (see Figure 1). It is clear that $G_{1}$ is a bipartite graph and $G_{2}$ is a chordal graph. Let $k = -5q$.

Let $G\in\{G_{1}, G_{2}\}$. Assume that $(X, C)$ has an exact cover $C'$. Define a function $f$ on $G$ as follows. Let $f(v) = -1$ for every leaf $v$ in $G$, let $f(x_{i}) = f(a_{i}) = 3$ for all $i\in[3q]$ and let $f(c_{j}) = 1$ if $C_{j}\notin C'$ and $f(c_{j}) = 2$ if $C_{j}\in C'$. It is clear to see that $f$ is an SDIDF of weight equal to $k$.

Conversely, assume that $G$ admits an SDIDF $f$ with $w(f)\le k$. Choose a $\gamma_{sdI}(G)$-function $f$ such that $|V_{-1}^{f}\cap L(G)|$ is maximum possible. So, $f(a_{i}) = f(x_{i}) = 3$ for every $i\in[3q]$ and $f(v) = -1$ for every $v\in L(G)$. As $\sum_{u\in N[a_{i}]}f(u)\ge1$, then $f(c_{i})\ge1$ for every $i\in[3q]$. As $\sum_{z\in N[x_{i}]}f(z)\ge1,$ then $\sum_{z\in N(x_{i})\backslash L(G)}f(z)\ge4$ for every $i\in[3q]$. Thus, $\sum_{i\in[3q]}f(c_{i})\ge\frac{4(3q)}{3} = 4q$. As $w(f)\le-5q$, then we must have $\sum_{i\in[3q]}f(c_{i}) = 4q$. So, $\sum_{z\in N(x_{i})\backslash L(G)}f(z) = 4$ for every $i\in[3q]$. Thus, every $x_{i}$ is a neighbor of only one $c_{j}$, with $f(c_{j}) = 2$. Hence, $C': = \{C_{j}\in C|f(c_{j}) = 2\}$ is an exact cover.

□

3.   Trees

In this section, we determine the tight lower and upper bounds of $\gamma_{sdI}(T)$, where $T$ is a tree, and we characterize trees achieving these bounds.

We start by determining $\gamma_{sdI}(G)$ of the paths and star graphs, and we give a tight lower bound for double star graphs, which are simple examples of trees.

Proposition 5. Let $n\ge1$, then

Proof. Let $A_{n} = \frac{n}{3}$ if $n\equiv0\;\;{\rm{mod}}\;{\rm{3}}$ and $A_{n} = \lfloor\frac{n}{3}\rfloor+2$ if $n\equiv1, 2\;\;{\rm{mod}}\;{\rm{3}}.$ Let $P_{n} = v_{1}v_{2}\cdots v_{n}$. First, we show that $\gamma_{sdI}(P_{n})\le A_{n}$. Define an SDIDF $f$ on $P_{n}$ as follows. If $n\equiv0\;\;{\rm{mod}}\;{\rm{3}}$, let $f(v_{3i-1}) = 3$ for every $i\in[\frac{n}{3}]$ and let $f = -1$ otherwise. If $n\equiv1{\mod3}$, let $f(v_{3i-1}) = 3$ for every $i\in[\lfloor\frac{n}{3}\rfloor]$, let $f(v_{n}) = 2$ and let $f = -1$ otherwise. If $n\equiv2{\mod3}$, let $f(v_{3i-1}) = 3$ for every $i\in[\lfloor\frac{n}{3}\rfloor]$, let $f(v_{n}) = 3$ and let $f = -1$ otherwise. Thus, $\gamma_{sdI}(P_{n})\le w(f) = A_{n}$.

Now, we show that $\gamma_{sdI}(P_{n}) = A_{n}.$ Let $f$ be a $\gamma_{sdI}(P_{n})$-function. Assume that $n\equiv0\;\;{\rm{mod}}\;{\rm{3}}$, then

Thus, we must have $\gamma_{sdI}(P_{n}) = w(f) = \frac{n}{3}$ as desired.

Assume that $n\equiv1\;\;{\rm{mod}}\;{\rm{3}}$. If $f(v_{n})\ge2$ (this case is symmetric to $f(v_{1})\ge2)$, then

as desired. Assume that $f(v_{n}) < 2$. If $f(v_{n}) = 1$, then $f(v_{n-1}) = 2$, so it is not possible to have $f(v_{n-2}) = f(v_{n-3}) = -1$. Thus,

as desired. If $f(v_{n}) = -1$, then $f(v_{n-1}) = 3$. Due to the symmetry of $P_{n}$, we can assume $f(v_{1}) = -1$ and $f(v_{2}) = 3$, then

a contradiction. Thus, $\gamma_{sdI}(P_{n}) = w(f) = A_{n}$.

Assume that $n\equiv2\;\;{\rm{mod}}\;{\rm{3}}$. If $f(v_{n-1})+f(v_{n})\ge2$, then

as desired. If $f(v_{n-1})+f(v_{n})\le1$, we must have $f(v_{n}) = 2$ and $f(v_{n-1}) = -1$. Due to the symmetry of $P_{n}$, we may assume that $f(v_{1}) = 2$ and $f(v_{2}) = -1$. Observe that $f(v_{3})\ge1$, so $f(N[v_{2}])\ge2$, then

as desired. Thus, $\gamma_{sdI}(P_{n}) = w(f) = A_{n}.$ □

Now, we give the exact SDID number of star graphs.

Proposition 6. Let $n\ge1$, then

Proof. Denote the vertex in the center by $c$ and denote the leaves by $v_{1}, \cdots, v_{n}$. Observe that $\gamma_{sdI}(K_{1, n}) = f(N[c])\ge1$, where $f$ is any SDIDF on $K_{1, n}$. From Proposition 5, we get $\gamma_{sdI}(K_{1, 1}) = 2$ and $\gamma_{sdI}(K_{1, 2}) = 1$. Assume that $n = 3$. By assigning value three to $c$, value negative one to each of $v_{1}$ and $v_{2}$ and value one to $v_{3}$, we get an SDIDF of weight equal to two, so $\gamma_{sdI}(K_{1, 3})\le2$. Clearly, $\gamma_{sdI}(K_{1, 3}) = 2$. Assume that $n\ge4$. Assign value three to $c$. If $n$ is even, assign value negative one to each of $v_{1}$ and $v_{2}$. For the remaining vertices, assign value one to $v_{i}$ if $i$ is even, and assign value negative one to $v_{i}$ if $i$ is odd. If $n$ is odd, assign value two to $v_{1}$ and assign value negative one to each of $v_{2}, v_{3}, v_{4}, v_{5}$. For the remaining vertices, assign value one to $v_{i}$ if $i$ is even and assign value negative one to $v_{i}$ if $i$ is odd. So, $\gamma_{sdI}(K_{1, n})\le1$, and, thus, $\gamma_{sdI}(K_{1, n}) = 1$. □

In Proposition 7, a tight lower bound of the SDID number of the double star graphs is given.

Proposition 7. Let $s\ge t\ge1$, then

(1) $\gamma_{sdI}(DS_{s, t})\ge-4$ and

(2) $\gamma_{sdI}(DS_{s, t})\ge\frac{-5(t+s+2)+24}{9}$, with equality if, and only if, $s = t = 5$.

Proof. Denote the non-leaf vertex with degree $s$ by $u$, the leaves adjacent to $u$ by $u_{1}, \cdots, u_{s}$; the non-leaf vertex with degree $t$ by $v$ and the leaves adjacent to $v$ by $v_{1}, \cdots, v_{t}$. Let $f$ be a $\gamma_{sdI}(DS_{s, t})$-function. Observe that $\gamma_{sdI}(DS_{s, t}) = f(N[u])+f(N[v])-f(u)-f(v)\ge1+1-3-3 = -4$. Thus, the first statement holds.

If $f(u)\le2$ (this case is symmetric to $f(v)\le2$), then $f(u_{i})\ge1$ for every $i\in[s]$. Thus,

as desired. So, we may assume that $f(u) = f(v) = 3$. If $s\le5$, then $\sum_{i = 1}^{i = s}f(u_{i}) = -s$; similarly, if $t\le5$, then $\sum_{i = 1}^{i = t}f(v_{i}) = -t$. If $s = 6$, then $\sum_{i = 1}^{i = s}f(u_{i}) = -4$; similarly if $t = 6$, then $\sum_{i = 1}^{i = t}f(v_{i}) = -4$. If $s\ge7$, then $\sum_{i = 1}^{i = s}f(u_{i}) = -5$; similarly if $t\ge7$, then $\sum_{i = 1}^{i = t}f(v_{i}) = -5$.

If $t, s\le5$ then

with equality if, and only if, $s = t = 5$. If $s = 6$ and $t\le5$, then

If $s = t = 6$, then

If $s\ge7$ and $t\le5$, then

If $s\ge7$ and $t = 6$, then

If $t, s\ge7$, then

Thus, the second statement holds. □

Let $\mathcal{C}$ be the set of all graphs that can be obtained from a tree $T$ by adding 3${\rm{d}}_{T}(v)+2$ pendant edges to $v$ for all $v\in T$. Next, we give the tight lower bound of the SDID number of the trees and characterize the trees achieving this bound.

Theorem 2. Let $T$ be a tree of order $n\ge2$, then

with equality if, and only if, $T\in\mathcal{C}$.

Proof. We use induction on the number of vertices. If $n = 2$, then $T = P_{2}$ and $\gamma_{sdI}(P_{2}) = 2 > \frac{-5n+24}{9}$. When $n = 3$, $T = P_{3}$ and $\gamma_{sdI}(P_{3}) = 1 = \frac{-5n+24}{9}$. Observe that $P_{3}\in\mathcal{C}$. This establishes the base step. Assume that $n\ge4$ and that the statement holds for every tree of order less than $n$. Let $f$ be a $\gamma_{sdI}(T)$-function, where $T$ is a tree of order $n$. If ${\rm{diam}}(T) = 2$, then $T = K_{1, n-1}$, so $\gamma_{sdI}(T)\ge1 > \frac{-5n+24}{9}$ (Proposition 6). If ${\rm{diam}}(T) = 3$, then $T = DS_{s, t}$ and $\gamma_{sdI}(T)\ge\frac{-5n+24}{9}$, with equality if, and only if, $T = DS_{5, 5}$ (Proposition 7). Observe that $DS_{5, 5}\in\mathcal{C}.$ So, we may assume that ${\rm{diam}}(T)\ge4$.

If $|V_{-1}^{f}|\le1$, then

and we are done. So, we may assume that $|V_{-1}^{f}|\ge2$. Assume that there exist two adjacent vertices $u, v\in V_{-1}^{f}$. Let $T_{1}$ and $T_{2}$ be the trees obtained from $T$ by deleting the edge $uv$. Clearly, $|T_{1}|, |T_{2}|\ge2$, and the restriction of $f$ on $T_{i}$ is an SDIDF on $T_{i}$. From the induction hypothesis,

and we are done. So, we may assume that for every two vertices $u, v\in V_{-1}^{f}$, ${\rm{dist}}_{T}(u, v)\ge2.$ The argument is divided into the following cases.

Case 1. There exists $x\in V_{-1}^{f}$ with ${\rm{d}}(x)\ge2$, then $x$ is not a leaf. Denote the leaves adjacent to $x$, if any, by $u_{1}, \cdots, u_{s}$, and denote the subtrees of order greater than one obtained from $T$ by deleting $x$ by $T_{1}, \cdots, T_{r}$. It is clear that $f_{i}: = f|_{T_{i}}$ is an SDIDF on $T_{i}$. Observe that $r\ge1$ as ${\rm{diam}}(T)\ge4$ and $f(u_{i})\ge2$ for all $i\in[s]$ (if $u_{i}$s exist). Observe also that if $r = 1$, then $s\ne0$, as ${\rm{d}}(x)\ge2$. From the induction hypothesis,

and we are done. So, we may assume that ${\rm{d}}(x) = 1$ for every $x\in V_{-1}^{f}$. In other words, every vertex in $V_{-1}^{f}$ is a leaf.

Case 2. There exists $x\in V_{1}^{f}$ with ${\rm{d}}(x)\ge2$. So, $V_{1}^{f}$ has a non-leaf vertex $x$. Denote the leaves adjacent to $x$, if any, by $u_{1}, \cdots, u_{s}$. So, $f(u_{i})\ge2$ for every $i\in[s]$ (if $u_{i}$s exist). Denote the subtrees of order greater than one that are obtained from $T$ by deleting $x$ by $T_{1}, \cdots, T_{r}$. Observe that $r\ge1$ as ${\rm{diam}}(T)\ge4$, and if $s = 0$, then $r\ge2$. Denote the unique vertex adjacent to $x$ in $T_{i}$ by $y_{i}$. Observe that $f(y_{i})\ge1$, as $y_{i}$ is a non-leaf vertex. For every $i\in[r]$, do the following. If $f(y_{i}) = 1$ or $2$, define an SDIDF $g$ on $T_{i}$ as $g(y_{i}) = f(y_{i})+1$ and $g(a) = f(a)$ for every $a\in T_{i}\backslash\{y_{i}\}$. If $f(y_{i}) = 3$ and $f(N[y_{i}])\ge2$, then $f_{i}: = f|_{T_{i}}$ is an SDIDF on $T_{i}$, and if $f(N[y_{i}]) = 1$ then, $y_{i}$ is adjacent to a vertex $w\in V_{-1}^{f}$. Define an SDIDF $g$ on $T_{i}$, as $g(w) = 1$ and $g(a) = f(a)$ for every $a\in T_{i}\backslash\{w\}$. From the induction hypothesis,

The last inequality follows from the fact that $r\ge1$, and if $r = 1$, then $s\ge1$. So, we may assume that every non-leaf vertex is assigned two or three.

Case 3. There exists $x\in V_{2}^{f}$ with ${\rm{d}}(x)\ge2$; in other words, $x$ is not a leaf. Denote the leaves adjacent to $x$, if any, by $u_{1}, \cdots, u_{s}$. So, $f(u_{i})\ge1$ for every $i\in[s]$ (if $u_{i}$s exist). Denote the subtrees of order greater than one that are obtained from $T$ by deleting $x$ by $T_{1}, \cdots, T_{r}$. Observe that $r\ge1$ as ${\rm{diam}}(T)\ge4$. As in the previous case, denote the unique vertex adjacent to $x$ in $T_{i}$ by $y_{i}$. Observe that $f(y_{i})\ge2$, as $y_{i}$ is a non-leaf vertex. For every $i\in[r]$, do the following. If $f(y_{i}) = 2$, define an SDIDF $g$ on $T_{i}$ as $g(y_{i}) = 3$ and $g(a) = f(a)$ for every $a\in T_{i}\backslash\{y_{i}\}$. If $f(y_{i}) = 3$ and $f(N[y_{i}])\ge3$, then $f_{i}: = f|_{T_{i}}$ is an SDIDF on $T_{i}$, and if $f(N[y_{i}])\in\{1, 2\}$, then $y_{i}$ is adjacent to a vertex $w\in V_{-1}^{f}$. Define a SDIDF $g$ on $T_{i}$, as $g(w) = 1$ and $g(a) = f(a)$ for every $a\in T_{i}\backslash\{w\}$. From the induction hypothesis,

The last inequality follows from the fact that $r\ge1$.

So, we may assume that all non-leaf vertices are labeled three.

Case 4. There exists $x\in T$ such that $x$ is neither a leaf nor a support vertex. Let $N(x) = \{y_{1}, \cdots, y_{r}\}$, $r\ge2$. Observe that $f(x) = f(y_{i}) = 3$ for all $i\in[r]$. Let $T'$ be the tree obtained from $T$ be deleting $x$ and adding the set of edges $\{y_{i}y_{i+1}|i\in[r-1]\}$. Let $g$ be an SDIDF on $T'$ defined as $g(u) = f(u)$ for all $u\in T'$. From the induction hypothesis,

as required. So, assume $L(T)\cup S(T) = V(T)$.

Assume that there exists a leaf $y$ such that $f(y)\ge1$. Denote the support vertex adjacent to $y$ by $x$. Recall that $f(x) = 3$. Since $f$ is a $\gamma_{sdI}(G)$-function, there are three leaves $z_{i}, i\in[3]$ in $N(x)$ such that $f(z_{i}) = -1$ for all $i\in[3].$ Let $T' = T-\{z_{1}, y\}$ if $f(y) = 1$, let $T' = T-\{z_{1}, z_{2}, y\}$ if $f(y) = 2$ and let $T' = T-\{z_{1}, z_{2}, z_{3}, y\}$ if $f(y) = 3$. Define an SDIDF $g$ on $T'$ by setting $g(v) = f(v)$ for all $v\in T'$. Then,

so the statement holds.

So, we may assume that all leaves are labeled negative one.

Let $T' = T-V_{-1}^{f}$. It can be seen that for every support vertex $x\in T$, the number of leaves adjacent to $x$ in $T$ is at most $3{\rm{d}}_{T'}(x)+2$. It is well known that for any graph $G,$ $\sum_{v\in G}{\rm{d}}(v) = 2|E(G)|$. It is also well known that for any tree $T$, $|E(T)| = |T|-1$. Thus,

So,

Now,

where inequality $(*)$ follows from Eq $(3.1)$. Observe that the equality holds if $|V_{-1}^{f}| = 8|T'|-6$, i.e., every $x\in T'$ is adjacent to $3{\rm{d}}_{T'}(x)+2$ leaves.

Conversely, assume that $T\in\mathcal{C}.$ Let $h$ be an SDIDF on $T$ such that $h(v) = -1$ if $v$ is a leaf and $h(v) = 3$ if $v$ is a support vertex. Then, $\gamma_{sdI}(T)\le w(h) = \frac{-5n+24}{9}$, and, thus, $\gamma_{sdI}(T) = \frac{-5n+24}{9}.$ □

Proposition 8. Let $T$ be a tree with $|T|\ge2$, then

(1) $\gamma_{sdI}(T)\le |T|$ and

(2) $\gamma_{sdI}(T) = |T|$ if, and only if, $T = P_{2}$.

Proof. It follows directly from Proposition 1 and the fact that $\gamma_{sdR}(T)\le |T|$ ^[15]. □ For the general graphs, we could not find a characterization for graphs $G$ satisfying $\gamma_{sdI}(G) = |G|$.

Proposition 9. Let $G$ be a connected graph with $|G|\ge3$. If $\gamma_{sdI}(G) = |G|$, then $\delta(G)\ge2$.

Proof. Assume for contrast that $\delta(G) = 1$. From Proposition 6, $G\ne K_{1, |G|-1}$. From Proposition 4, $G$ does not have a strong support vertex. So, all the support vertices are weak. Let $v$ be one of the weak support vertices. Denote the leaf adjacent to $v$ by $u$. If $v$ is adjacent to a vertex $w$ such that ${\rm{d}}(w) = 2$ and $w$ is not a support vertex, assign value negative one to $u$ and $w$, value three to $v$, value two to the other neighbor of $w$, value three to each of the remaining support vertices, value negative one to each of the remaining leaves, and value one to the remaining vertices. If all the non-leaf neighbors of $v$ are support vertices or have a degree greater than two, assign value two to $u$, assign value negative to $v$, assign value three to each of the remaining support vertices, assign value negative one to each of the remaining leaves, and assign value one to remaining vertices. Clearly this labeling is an SDIDF of weight less than $|G|$, so $\gamma_{sdI}(G) < |G|$; a contradiction. Thus, $\delta(G)\ge2$. □

4.   SDID for well-known graphs

In this section, $\gamma_{sdI}(G)$ is determined for cycle graphs and the Petersen graph.

Proposition 10. Let $C_{n}$ be a cycle graph of order $n$, then

Proof. Let $C_{n} = v_{1}v_{2}\cdots v_{n}.$ Assume that $n$ is a multiple of three. Assume that $f$ is an SDIDF on $C_{n}$, then $w(f) = \sum_{i\equiv2\mod3}f(N[v_{i}])\ge\sum_{i\equiv2\mod3}1 = \frac{n}{3}$. Thus, $\gamma_{sdI}(C_{n})\ge\frac{n}{3}$. Now, we show that $\frac{n}{3}$ is sufficient. Set $\text{g}(v_{i}) = 3$ if $i\equiv2\mod3$ and set $g(v_{i}) = -1$ otherwise, then $g$ is an SDIDF on $C_{n}$ with $w(g) = \frac{n}{3}$. Thus, $\gamma_{sdI}(C_{n})\le\frac{n}{3}$. Therefore, $\gamma_{sdI}(C_{n}) = \frac{n}{3}$ if $n$ is a multiple of three.

Assume that $n$ is not a multiple of three. We use induction on $n$. It is easy to check that $\gamma_{sdI}(C_{4}) = 4$ and $\gamma_{sdI}(C_{5}) = 3.$ Assume that there exists an SDIDF $f$ with $w(f)\le a_{n}-1$, where $a_{n} = \frac{n-4}{3}+4$ if $n\equiv1\mod3$ and $a_{n} = \frac{n-2}{3}+2$ if $n\equiv2\mod3$.

Claim 1. $a_{n}-2 < a_{n-3}$.

Proof. If $a_{n} = \frac{n-4}{3}+4$, then

If $a_{n} = \frac{n-2}{3}+2,$ then

□ Among all the pair of vertices in $V_{-1}^{f}$, choose $x, y$ such that ${\rm{dist}}(x, y)$ is minimum possible. We have three cases.

Case 1. ${\rm{dist}}(x, y) = 1$.

Say that $x = v_{i}$ and $y = v_{i+1}$. Observe that $v_{i-1}$ and $v_{i+2}$ each are assigned value of three. Contract the path $v_{i-1}v_{i}v_{i+1}v_{i+2}$ into a vertex $v$. The resulting graph is $C_{n-3}$. Define an SDIDF $g$ on $C_{n-3}$ by setting $g(v) = 3$ and $g(u) = f(u)$ for all $u\in V(C_{n-3})\backslash\{v\}$, then $w(g) = w(f)-1\le a_{n}-2 < a_{n-3}$, contradicting the induction hypothesis. So, the statement holds.

Case 2. ${\rm{dist}}(x, y) = 2$.

Say that $x = v_{i}$ and $y = v_{i+2}$. We must have $f(v_{i+1}) = 3$ and $f(v_{i+3})\ge1.$ Contract the path $v_{i}v_{i+1}v_{i+2}v_{i+3}$ into a vertex $v$. The resulting graph is the cycle $C_{n-3}$. Define an SDIDF $g$ on $C_{n-3}$ as follows. Set $g(v) = f(v_{i+3})$ and $g(u) = f(u)$ for all $u\in V(C_{n-3})\backslash\{v\}$, then, $w(g)\le w(f)-1\le a_{n}-2 < a_{n-3}$, contradicting the induction hypothesis. So, the statement holds.

Case 3. ${\rm{dist}}(x, y)\ge3$.

Say that $x = v_{i}$, then $f(v_{i-2}), f(v_{i-1}), f(v_{i+1}), f(v_{i+2})\ge1.$ Contract the path $v_{i-1}v_{i}v_{i+1}v_{i+2}$ into a vertex $v$. The resulting graph is the cycle $C_{n-3}$. Define an SDIDF $g$ on $C_{n-3}$ as follows. Set $g(v) = \max\{f(v_{i-1}), f(v_{i+1}), f(v_{i+2})\}$ and $g(u) = f(u)$ for all $u\in V(C_{n-3})\backslash\{v\}$, then $w(g)\le w(f)-1\le a_{n}-2 < a_{n-3}$, contradicting the induction hypothesis. So, the statement holds. □

Proposition 11. The SDID number for the Petersen graph is five.

Proof. Let $G$ be the Petersen graph with vertices labeled as in Figure 2. Define an SDIDF $f$ on $G$ as follows. Set $f(x_{1}) = f(x_{4}) = f(y_{2}) = f(y_{3}) = -1,$ set $f(x_{2}) = f(y_{4}) = f(y_{5}) = 1$ and set $f(x_{3}) = f(x_{5}) = f(y_{1}) = 2$, then $\gamma_{sdI}(G)\le w(f) = 5$. To show that five is tight, assume that $G$ admits an SDIDF $g$ of weight less than five, then $|V_{-1}^{g}|\ge3$. We divide the argument into two cases.

Case 1. There are $u, v\in V_{-1}^{g}$ with $uv \in E$.

Due to the symmetry of the Petersen graph, assume that $g(x_{1}) = g(x_{2}) = -1$, then $g(x_{5})+g(y_{1})\ge$$3$ and, similarly, $g(x_{3})+g(y_{2})\ge3$. Thus, at least two vertices from the remaining vertices, i.e., $x_{4}, y_{3}, y_{4}, y_{5}$, are assigned value negative one. Note that it is impossible to have $\{y_{3}, y_{4}\}\subseteq V_{-1}^{g}$, as we would have $g(N[y_{1}])\le0$; similarly, it is impossible to have $\{y_{4}, y_{5}\}\subseteq V_{-1}^{g}$, as we would have $g(N[y_{2}])\le0.$ It is also impossible to have $\{x_{4}, y_{5}\}\subseteq V_{-1}^{g}$, as we would have $g(N[x_{5}])\le0$, and it is impossible to have $\{x_{4}, y_{3}\}\subseteq V_{-1}^{g}$, as we would have $g(N[x_{3}])\le0$. Thus, we are left with two sub-cases. The first sub-case is $\{x_{4}, y_{4}\}\subseteq V_{-1}^{g}$ and $\{y_{3}, y_{5}\}\subseteq V_{1}^{g}$, and the second sub-case is $\{y_{3}, y_{5}\}\subseteq V_{-1}^{g}$ and $\{x_{4}, y_{4}\}\subseteq V_{1}^{g}$. If we are in the first sub-case, we must have $g(x_{3}), g(x_{5}), g(y_{1}), g(y_{2})\ge2$. Thus, $w(g) > 4$, a contradiction. We get the same result if we are in the second sub-case. Thus, Case $1$ is impossible.

Case 2. $V_{-1}^{g}$ is an independent set.

Due to the symmetry of $G$, we may assume that $g(x_{1}) = g(x_{3}) = -1.$ As each of $x_{2}, x_{4}, x_{5}, y_{1}, y_{3}$ is adjacent to $x_{1}$ or $x_{3}$, then $g(v)\ge 1$ for all $v\in \{x_{2}, x_{4}, x_{5}, y_{1}, y_{2}\}$. Note that $g(y_{2})\ge1$ or else we would have $g(N[x_{2}])\le0,$ which is a contradiction. Thus, either $g(y_{4}) = -1$ or $g(y_{5}) = -1$. Due to the symmetry of $G$, we may assume that $g(y_{4}) = -1$. As $w(g)\le4$, then $y_5$ is assigned one or negative one. If $g(y_{5}) =$$1$, then $g(x_{2}), g(x_{4}), g(x_{5}), g(y_{1}), g(y_{2}) = 1$, but now we have $g(N[x_{2}]) = 0$; a contradiction. Thus, $g(y_{5}) =$$-1$. Observe that it is impossible to have $g(x_{2}) = g(y_{2}) = 1$, as we would have $g(N[x_{2}]) = 0$, so $g(x_{2})+g(y_{2})\ge3$. Similarly, it is impossible to have $g(y_{1}) = g(y_{3}) = 1$, as we would have $g(N[y_{1}]) = 0$, so $g(y_{1})+g(y_{3})\ge3$. It is also impossible to have $g(x_{4}) = g(x_{5}) = 1$, as we would have $g(N[x_{5}]) = 0$, so $g(x_{4})+(x_{5})\ge3.$ Thus, $w(g)\ge3(3)-4 = 5$; a contradiction. Hence, the statement holds. □

5.   Open problems

We conclude this work with two open problems.

Problem 1. Characterize connected graphs $G$ with $|G|\ge3$, satisfying $\gamma_{sdI}(G) = |G|.$

Problem 2. Give characterizations for graphs $G$ satisfying $\gamma_{sdI}(G) = \gamma_{sdR}(G).$

Use of AI tools declaration

The author declares she has not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported by the Deanship of Scientific Research, Vice Presidency for Graduate Studies and Scientific Research, King Faisal University, Saudi Arabia [Grant No. 4988].

Conflict of interest

The author declares that she has no conflict of interest.