Signed Roman $k$-Domination in Graphs

Abstract

Let $k\ge 1$ be an integer, and let $G$ be a finite and simple graph with vertex set $V(G)$. A signed Roman $k$-dominating function (SRkDF) on a graph $G$ is a function $f:V(G)\rightarrow \{-1,1,2\}$ satisfying the conditions that (i) $\sum _{x\in N[v]}f(x)\ge k$ for each vertex $v\in V(G)$, where $N[v]$ is the closed neighborhood of $v$, and (ii) every vertex $u$ for which $f(u)=-1$ is adjacent to at least one vertex $v$ for which $f(v)=2$. The weight of an SRkDF $f$ is $w(f)=\sum _{v\in V(G)}f(v)$. The signed Roman $k$-domination number $\gamma _{sR}^k(G)$ of $G$ is the minimum weight of an SRkDF on $G$. In this paper we initiate the study of the signed Roman $k$-domination number of graphs, and we present different bounds on $\gamma _{sR}^k(G)$. In addition, we determine the signed Roman $k$-domination number of some classes of graphs. Some of our results are extensions of well-known properties of the signed Roman domination number $\gamma _{sR}(G)=\gamma _{sR}^1(G)$, introduced and investigated by Ahangar et al. (J Comb Optim doi:10.1007/s10878-012-9500-0, 2014).

1 Terminology and Introduction

For notation and graph theory terminology, we in general follow Haynes, Hedetniemi and Slater [6]. Specifically, let $G$ be a graph with vertex set $V(G)=V$ and edge set $E(G)=E$. The integers $n=n(G)=|V(G)|$ and $m=m(G)=|E(G)|$ are the order and the size of the graph $G$, respectively. The open neighborhood of vertex $v$ is $N_G(v)=N(v)=\left\{ u\in V(G)|uv\in E(G)\right\}$, and the closed neighborhood of $v$ is $N_G[v]=N[v]=N(v)\cup \{v\}$. The degree of a vertex $v$ is $d_G(v)=d(v)=|N(v)|$. The minimum and maximum degree of a graph $G$ are denoted by $\delta (G)=\delta$ and $\Delta (G)=\Delta$, respectively. If $X\subseteq V(G)$, then $G[X]$ is the subgraph induced by $X$. For a set $X\subseteq V(G)$, its open neighborhood is the set $N_G(X)=N(X)=\bigcup _{v\in X}N(v)$, and its closed neighborhood is the set $N_G[X]=N[X]=N(X)\cup X$. For disjoint subsets $X$ and $Y$ of vertices of a graph $G$, we denote by $(X,Y)$ the set of edges between $X$ and $Y$. The complement of a graph $G$ is denoted by $\overline{G}$. For sets $A,B\subseteq V(G)$, we say that $A$ dominates $B$ if $B\subseteq N[A]$. Let $K_n$ be the complete graph of order $n$ and $K_{p,p}$ the complete bipartite graph of order $2p$.

A rooted tree $T$ distinguishes one vertex $r$ called the root. For each vertex $v \ne r$ of $T$, the parent of $v$ is the neighbor of $v$ on the unique $(r,v)$-path, while a child of $v$ is any other neighbor of $v$. A descendant of $v$ is a vertex $u \ne v$ such that the unique $(r,u)$-path contains $v$. We let $D(v)$ denote the set of descendants of $v$. A leaf of $T$ is a vertex of degree $1$, while a support vertex of $T$ is a vertex adjacent to a leaf.

In this paper we continue the study of Roman dominating functions in graphs and digraphs. For a subset $S \subseteq V(G)$ of vertices of a graph $G$ and a function $f :V(G) \longrightarrow \mathbb {R}$, we define $f(S) = \sum _{x \in S} f(x)$. For a vertex $v$, we denote $f(N[v])$ by $f[v]$ for notational convenience.

If $k\ge 1$ is an integer, then the signed Roman $k$ -dominating function (SRkDF) on a graph $G$ is defined as a function $f:V(G)\longrightarrow \{-1,1,2\}$ such that $f[v] \ge k$ for every $v \in V(G)$, and every vertex $u$ for which $f(u)=-1$ is adjacent to a vertex $v$ for which $f(v)=2$.

The weight of an SRkDF $f$ on a graph $G$ is $\omega (f)=\sum _{v\in V(G)}f(v)$. The signed Roman $k$ -domination number $\gamma _{sR}^k(G)$ of $G$ is the minimum weight of an SRkDF on $G$. The special case $k=1$ was introduced and investigated by Ahangar et al. [1]. Sheikholeslami and Volkmann [8] studied the signed Roman domination number in digraphs.

A $\gamma _{sR}^k(G)$-function is a signed Roman $k$-dominating function on $G$ of weight $\gamma _{sR}^k(G)$. For an SRkDF $f$ on $G$, let $V_i=V_i(f)=\{v\in V(G):f(v)=i\}$ for $i=-1,1,2$. A signed Roman $k$-dominating function $f:V(G) \longrightarrow \{-1,1,2\}$ can be represented by the ordered partition $(V_{-1},V_1,V_2)$ of $V(G)$.

A signed dominating function (SDF) on a graph $G=(V,E)$ is a function $f :V \rightarrow \{-1,1\}$ such that $f[v] \ge 1$ for every vertex $v \in V$. Thus a signed Roman $k$-dominating function combines the properties of both a Roman dominating function and a signed dominating function. The signed domination number, denoted $\gamma _s(G)$, is the minimum weight of an SDF in $G$. Signed domination in graphs is well studied in the literature, see for example, [2–4, 7, 9] and elsewhere.

The signed Roman $k$-domination number exists when $\delta \ge \frac{k}{2}-1$. However, for investigations of the signed Roman $k$-dominating number it is reasonable to claim that $\delta (G)\ge k-1$. Thus we assume throughout this paper that $\delta (G)\ge k-1$. We present different bounds on $\gamma _{sR}^k(G)$. In addition, we determine the signed Roman $k$-domination number of some classes of graphs. Some of our results are extensions of well-known properties of the signed Roman domination number $\gamma _{sR}(G)=\gamma _{sR}^1(G)$, given by Ahangar et al. [1].

2 Preliminary Results

In this section we present basic properties of the signed Roman $k$-dominating functions and the signed Roman $k$-domination numbers. The definitions immediately lead to our first proposition.

Proposition 1

If $f=(V_{-1},V_1,V_2)$ is an SRkDF on a graph $G$ of order $n$, then

• (a) $|V_{-1}|+|V_1|+|V_2|=n$.

• (b) $\omega (f)=|V_1|+2|V_2|-|V_{-1}|$.

• (c) Every vertex in $V_{-1}$ is dominated by a vertex of $V_2$.

• (d) $V_1\cup V_2$ is a dominating set of $G$.

Proposition 2

Assume that $f=(V_{-1},V_1,V_2)$ is an SRkDF on a graph $G$ of order $n$. If $\delta (G)\ge k-1$, then

• (i) $(2\Delta +2-k)|V_2|+(\Delta +1-k)|V_1|\ge (\delta +k+1)|V_{-1}|$.

• (ii) $(2\Delta +\delta +3)|V_2|+(\Delta +\delta +2)|V_1|\ge (\delta +k+1)n$.

• (iii) $(\Delta +\delta +2)\omega (f)\ge (\delta -\Delta +2k)n+(\delta -\Delta )|V_2|$.

• (iv) $\omega (f)\ge (\delta -2\Delta +2k-1)n/(2\Delta +\delta +3)+|V_2|$.

Proof

• (i) It follows from Proposition 1 (a) that

  $$\begin{aligned} k\big (|V_{-1}|+|V_1|+|V_2|\big )&= kn\le \sum _{v\in V(G)}f[v]=\sum _{v\in V(G)}\left( d_G(v)+1\right) f(v)\\&= \sum _{v\in V_2}2\left( d_G(v)+1\right) + \sum _{v\in V_1}\left( d_G(v)+1\right) \nonumber \\&\quad - \sum _{v\in V_{-1}}\left( d_G(v)+1\right) \\&\le 2(\Delta +1)|V_2|+(\Delta +1)|V_1|-(\delta +1)|V_{-1}|. \end{aligned}$$

  This inequality chain yields to the desired bound in (i).

• (ii) Proposition 1 (a) implies that $|V_{-1}|=n-|V_1|-|V_2|$. Using this identiy and Part (i) of Proposition 2, we arrive at (ii).

• (iii) According to Proposition 1 and Part (ii) of Proposition 2, we obtain Part (iii) of Proposition 2 as follows

  $$\begin{aligned} (\Delta +\delta +2)\omega (f)&= (\Delta +\delta +2)(2(|V_1|+|V_2|)-n+|V_2|)\\&\ge 2(\delta +k+1)n-2(\Delta +1)|V_2|+(\Delta +\delta +2)(|V_2|-n)\\&= (\delta -\Delta +2k)n+(\delta -\Delta )|V_2|. \end{aligned}$$

• (iv) The inequality chain in the proof of Part (i) and Proposition 1 (a) show that

  $$\begin{aligned} kn&\le 2(\Delta +1)|V_1\cup V_2|-(\delta +1)|V_{-1}|\\&= 2(\Delta +1)|V_1\cup V_2|-(\delta +1)(n-|V_1\cup V_2|)\\&= (2\Delta +\delta +3)|V_1\cup V_2|-(\delta +1)n \end{aligned}$$

  and thus

  $$\begin{aligned} |V_1\cup V_2|\quad \ge \quad \frac{n(\delta +k+1)}{2\Delta +\delta +3}. \end{aligned}$$

  Using this inequality and Proposition 1, we obtain

  $$\begin{aligned} \omega (f)&= 2|V_1\cup V_2|-n+|V_2|\\&\ge \frac{n(2\delta +2k+2-2\Delta -\delta -3)}{2\Delta +\delta +3}+|V_2|\\&= \frac{n(\delta -2\Delta +2k-1)}{2\Delta +\delta +3}+|V_2|. \end{aligned}$$

  This is the bound in Part (iv), and the proof is complete.

$\square$

3 Bounds on the Signed Roman $k$-Domination Number

We start with some simple upper bounds on the signed Roman $k$-domination number of a graph.

Theorem 3

Let $G$ be a graph of order $n$ with $\delta (G)\ge k-1$. Then $\gamma _{sR}^k(G)\le n$. If $\delta (G)\ge k+2t-1$ for an integer $t\ge 1$, then $\gamma _{sR}^k(G)\le n-t$.

Proof

Define the function $f:V(G)\longrightarrow \{-1,1,2\}$ such that $f(x)=1$ for each vertex $x\in V(G)$. Since $\delta (G)\ge k-1$, the function $f$ is an SRkDF on $G$ of weight $n$ and thus $\gamma _{sR}^k(G)\le n$.

Let now $\delta (G)\ge k+2t-1$ for an integer $t\ge 1$. Let $A=\{u_1,u_2,\ldots ,u_t\}$ be a set of $t$ vertices in $V(G)$, and let $B=\{v_1,v_2,\ldots ,v_t\}$ be a set of $t$ vertices such that $v_i\in V(G)-A$ and $v_i$ is adjacent to $u_i$ for $1\le i\le t$. Define the function $g :V(G) \longrightarrow \{-1,1,2\}$ such that $g(u_i)=-1$, $g(v_i)=2$ for $1\le i\le t$ and $g(x)=1$ for $x\in V(G)-(A\cup B)$. Then $g[u_i]\ge k+1$, $g[v_i]\ge k+1$ for $1\le i\le t$ and $g[x]\ge k$ for $x\in V(G)-(A\cup B)$. Therefore $g$ is an SRkDF on $G$ of weight $n-t$ and thus $\gamma _{sR}^k(G)\le n-t$. $\square$

As an application of Proposition 2 (iii), we obtain a lower bound on the signed Roman $k$-domination number for $r$-regular graphs.

Corollary 4

If $G$ is an $r$-regular graph of order $n$ with $r\ge k-1$, then

$$\begin{aligned} \gamma _{sR}^k(G)\ge \frac{kn}{r+1}. \end{aligned}$$

Example 5

If $H$ is a $(k-1)$-regular graph of order $n$, then it follows from Corollary 4 that $\gamma _{sR}^k(H)\ge n$ and thus $\gamma _{sR}^k(H)=n$, according to Theorem 3.

Example 5 shows that Theorem 3 and Corollary 4 are both sharp.

Theorem 6

If $G$ is a graph of order $n$ with $\delta (G)\ge k-1$, then

$$\begin{aligned} \gamma _{sR}^k(G)\ge k+1+\Delta (G)-n. \end{aligned}$$

Proof

Let $w\in V(G)$ be a vertex of maximum degree, and let $f$ be a $\gamma _{sR}^k(G)$-function. Then the definitions imply

$$\begin{aligned} \gamma _{sR}^k(G)&= \sum _{x\in V(G)}f(x)=\sum _{x\in N[w]}f(x)+\sum _{x\in V(G)-N[w]}f(x)\\&\ge k+\sum _{x\in V(G)-N[w]}f(x)\ge k-\big (n-(\Delta (G)+1)\big )=k+1+\Delta (G)-n, \end{aligned}$$

and the proof of the desired lower bound is complete. $\square$

In Ahangar et al. [1] it was shown that $\gamma _{sR}(K_3)=2$ and $\gamma _{sR}(K_n)=1$ for $n\ne 3$. In the next example we determine $\gamma _{sR}^k(K_n)$ for $k\ge 2$.

Example 7

If $n\ge k\ge 2$ are integers, then $\gamma _{sR}^k(K_n)=k$.

Proof

Corollary 4 implies that $\gamma _{sR}^k(K_n)\ge k$. If $n=k$, then it follows from Theorem 3 that $\gamma _{sR}^k(K_n)\le n=k$ and thus the desired result in that case. Now let $n\ge k+1$. We distinguish two cases.

Case 1. Assume that $n-k$ is even. Let the function $f:V(K_n)\longrightarrow \{-1,1,2\}$ assign to two vertices the value 2, to $(n+k-6)/2$ vertices the value 1 and to $(n-k+2)/2$ vertices the value $-$1. Then $f$ is an SRkDF on $K_n$ of weight $\omega (f)=k$, and so $\gamma _{sR}^k(K_n)\le k$. Consequently, $\gamma _{sR}^k(K_n)=k$ in that case.

Case 2. Assume that $n-k$ is odd. Let the function $f:V(K_n)\longrightarrow \{-1,1,2\}$ assign to one vertex the value 2, to $(n+k-3)/2$ vertices the value 1 and to $(n-k+1)/2$ vertices the value $-$1. Then $f$ is an SRkDF on $K_n$ of weight $\omega (f)=k$, and so $\gamma _{sR}^k(K_n)\le k$. Consequently, $\gamma _{sR}^k(K_n)=k$ in that case. $\square$

Example 7 shows that Theorem 6 is sharp.

Corollary 8

Let $G$ be a graph of order $n$, minimum degree $\delta \ge k-1$ and maximum degree $\Delta$. If $\delta <\Delta$, then

$$\begin{aligned} \gamma _{sR}^k(G)\ge \left( \frac{-2\Delta ^2+2\Delta \delta +3k\Delta -2\Delta +2\delta +3k}{(\Delta +1)(2\Delta +\delta +3)}\right) n. \end{aligned}$$

Proof

Multiplying both sides of the inequality in Proposition 2 (iv) by $\Delta -\delta$ and adding the resulting inequality to the inequality in Proposition 2 (iii), we obtain the desired lower bound. $\square$

Example 9

Case 1. Assume that $k=2t+1$ for an integer $t\ge 1$.

Let $A_1,A_2,A_3,B_1,B_2,B_3$ be isomorphic to the complete graph $K_{2t-1}$, and let $H_1,H_2$ be isomorphic to the complete graph $K_{2t}$. Let $A=A_1\cup A_2\cup A_3$, $B=B_1\cup B_2\cup B_3$ and $H=H_1\cup H_2$. Now let $G$ be the disjoint union of $H,A$ and $B$ such that each vertex of $A$ is adjacent to each vertex of $H_1$, each vertex of $B$ is adjacent to each vertex of $H_2$, and $G[V(H)]$ is $(4t-2)$-regular. Then $\delta (G)=4t-2$, $\Delta (G)=10t-5$ and $n(G)=16t-6$.

Define the function $f:V(G)\longrightarrow \{-1,1,2\}$ by $f(x)=-1$ for $x\in V(A\cup B)$ and $f(x)=2$ for $x\in V(H)$. It is easy to verify that $f[x]=k$ for each vertex $x\in V(G)$. Therefore $f$ is an SRkDF on $G$ of weight $\omega (f)=6-4t$, and so $\gamma _{sR}^k(G)\le 6-4t$. Corollary 8 implies $\gamma _{sR}^k(G)\ge 6-4t$ and thus $\gamma _{sR}^k(G)=6-4t$.

Case 2. Assume that $k=4t$ for an integer $t\ge 1$.

Let $A_1,A_2,A_3,A_4,B_1,B_2,B_3,B_4$ be isomorphic to the complete graph $K_{2t}$, and let $H_1,H_2$ be isomorphic to the complete graph $K_{3t}$. Let $A=A_1\cup A_2\cup A_3\cup A_4$, $B=B_1\cup B_2\cup B_3\cup B_4$ and $H=H_1\cup H_2$. Now let $G$ be the disjoint union of $H,A$ and $B$ such that each vertex of $A$ is adjacent to each vertex of $H_1$, each vertex of $B$ is adjacent to each vertex of $H_2$, and each vertex of $H_1$ is adjacent to each vertex of $H_2$. Then $\delta (G)=5t-1$, $\Delta (G)=14t-1$ and $n(G)=22t$.

Define the function $f:V(G)\longrightarrow \{-1,1,2\}$ by $f(x)=-1$ for $x\in V(A\cup B)$ and $f(x)=2$ for $x\in V(H)$. It is easy to verify that $f[x]=k$ for each vertex $x\in V(G)$. Therefore $f$ is an SRkDF on $G$ of weight $\omega (f)=-4t$, and so $\gamma _{sR}^k(G)\le -4t$. Corollary 8 implies $\gamma _{sR}^k(G)\ge -4t$ and thus $\gamma _{sR}^k(G)=-4t$.

Case 3. Assume that $k=4t+2$ for an integer $t\ge 1$.

Let $A_1,A_2,A_3,A_4,B_1,B_2,B_3,B_4$ be isomorphic to the complete graph $K_{2t}$, and let $H_1,H_2$ be isomorphic to the complete graph $K_{3t+1}$. Let $A=A_1\cup A_2\cup A_3\cup A_4$, $B=B_1\cup B_2\cup B_3\cup B_4$ and $H=H_1\cup H_2$. Now let $G$ be the disjoint union of $H,A$ and $B$ such that each vertex of $A$ is adjacent to each vertex of $H_1$, each vertex of $B$ is adjacent to each vertex of $H_2$, and $G[V(H)]$ is $(6t)$-regular. Then $\delta (G)=5t$, $\Delta (G)=14t$ and $n(G)=22t+2$.

Define the function $f:V(G)\longrightarrow \{-1,1,2\}$ by $f(x)=-1$ for $x\in V(A\cup B)$ and $f(x)=2$ for $x\in V(H)$. It is easy to verify that $f[x]=k$ for each vertex $x\in V(G)$. Therefore $f$ is an SRkDF on $G$ of weight $\omega (f)=4-4t$, and so $\gamma _{sR}^k(G)\le 4-4t$. Corollary 8 implies $\gamma _{sR}^k(G)\ge 4-4t$ and thus $\gamma _{sR}^k(G)=4-4t$.

Example 9 demonstrates that Corollary 8 is sharp for $k\ge 3$. The next example shows that Corollary 8 is sharp for $k=1$ and $k=2$ too.

Example 10

Case 1. Let $\{x_1,x_2,x_3,y_1,y_2,y_3,x,y\}$ be the vertex set of the graph $G$ such that $x_i$ is adjacent to $x$, $y_i$ is adjacent to $y$ for $1\le i\le 3$ and $x$ is adjacent to $y$.

Define the function $f:V(G)\longrightarrow \{-1,1,2\}$ by $f(x_i)=f(y_i)=-1$ for $1\le i\le 3$ and $f(x)=f(y)=2$. Then $f[u]=1$ for each vertex $u\in V(G)$. Therefore $f$ is an SR1DF on $G$ of weight $\omega (f)=-2$, and so $\gamma _{sR}^1(G)\le -2$. Corollary 8 implies $\gamma _{sR}^1(G)\ge -2$ and thus $\gamma _{sR}^1(G)=\gamma _{sR}(G)=-2$.

Case 2. Let $A_1,A_2,A_3,B_1,B_2,B_3,H_1,H_2$ be isomorphic to the complete graph $K_{2}$. Let $A=A_1\cup A_2\cup A_3$, $B=B_1\cup B_2\cup B_3$ and $H=H_1\cup H_2$. Now let $G$ be the disjoint union of $H,A$ and $B$ such that each vertex of $A$ is adjacent to each vertex of $H_1$, each vertex of $B$ is adjacent to each vertex of $H_2$, and each vertex of $H_1$ is adjacent to each vertex of $H_2$. Then $\delta (G)=3$, $\Delta (G)=9$ and $n(G)=16$.

Define the function $f:V(G)\longrightarrow \{-1,1,2\}$ by $f(x)=-1$ for $x\in V(A\cup B)$ and $f(x)=2$ for $x\in V(H)$. Then $f[x]=2$ for each vertex $x\in V(G)$. Therefore $f$ is an SR2DF on $G$ of weight $\omega (f)=-4$, and so $\gamma _{sR}^2(G)\le -4$. Corollary 8 implies $\gamma _{sR}^2(G)\ge -4$ and thus $\gamma _{sR}^2(G)=-4$.

The special case $k=1$ of Proposition 2 and Corollaries 4, 8 can be found in Ahangar et al. [1].

A set $S\subseteq V(G)$ is a 2-packing of the graph $G$ if $N[u]\cap N[v]=\emptyset$ for any two distinct vertices $u,v\in S$. The 2-packing number $\rho (G)$ of $G$ is defined by

$$\begin{aligned} \rho (G)=\max \big \{|S|: S\,\,\mathrm{is \,\,a\,\, 2-packing\,\ of}\,\,G\big \}. \end{aligned}$$

Theorem 11

If $G$ is a graph of order $n$ with $\delta (G)\ge k-1$, then

$$\begin{aligned} \gamma _{sR}^k(G)\ge \rho (G)\left( k+\delta (G)+1\right) -n. \end{aligned}$$

Proof

Let $\{v_1,v_2,\ldots ,v_{\rho (G)}\}$ be a 2-packing of $G$, and let $f$ be a $\gamma _{sR}^k(G)$-function. If we define the set $A= \cup _{i=1}^{\rho (G)} N[v_i]$, then since $\{v_1,v_2,\ldots ,v_{\rho (G)}\}$ is a 2-packing, we have that

$$\begin{aligned} |A| = \sum _{i=1}^{\rho (G)} \left( d(v_i) + 1\right) \ge \rho (G)\left( \delta (G)+1\right) \!. \end{aligned}$$

It follows that

$$\begin{aligned} \gamma _{sR}^k(G)&= \sum _{x\in V(G)}f(x)=\sum _{i=1}^{\rho (G)}f[v_i]+\sum _{x\in V(G)-A}f(x)\\&\ge k\rho (G)+\sum _{x\in V(G)-A}f(x)\ge k\rho (G)-n+|A|\\&\ge k\rho (G)-n+\rho (G)\left( \delta (G)+1\right) =\rho (G)\left( k+\delta (G)+1\right) -n. \end{aligned}$$

$\square$

We show next that the bound in Theorem 11 is sharp. For integers $s \ge k \ge 2$ and $t \ge 1$, let $G$ be a graph of order $st$ obtained as follows: Let $F$ be an arbitrary graph of order $t$ and for each vertex $v \in V(F)$ add a vertex-disjoint copy of a complete graph $K_s$ and identify the vertex $v$ with one vertex of the added complete graph. Let $G$ denote the resulting graph. Further, let $G_1,G_2,\ldots ,G_t$ be the added copies of $K_s$. For $i = 1,2,\ldots ,t$, let $v_i$ be the vertex of $G_i$ that is identified with a vertex of $F$. Thus, $G\big [\{v_1,v_2,\ldots ,v_t\}\big ] \cong F$. We now construct a signed Roman $k$-dominating function on $G$ as follows. For each $i= 1,2,\ldots ,t$, let $f_i :V(G_i) \longrightarrow \{-1,1,2\}$ be the SRkDF on the complete graph $G_i \cong K_s$ defined as in Example 7. We note that the function $f_i$ assigns to at least one vertex of $G_i$ the value $2$. We choose $v_i$ to be one such vertex of $G_i$, and so $f_i(v_i) = 2$. As shown in Example 7, we have $w(f_i) = k$. Now let $f :V(G) \longrightarrow \{-1,1,2\}$ be the function defined by $f(v) = f_i(v)$ for each vertex $v \in V(G_i)$, and so $f = \bigcup _{i=1}^t f_i$. If $v = v_i$ for some $i$, $1 \le i \le t$, then $f[v] \ge f_i[v]$ with strict inequality if the vertex corresponding to $v_i$ is not isolated in $F$. If $v \ne v_i$ for any $i$, $1 \le i \le t$, then $f[v] = f_i[v]$. Hence, the function $f$ is an SRkDF of $G$, and so $\gamma _{sR}^k(G) \le w(f) = \sum _{i=1}^k w(f_i) = tk$. However by Theorem 11, and noting that here $\delta (G) = s - 1$, $\rho (G) = t$, and $n(G) = st$, we have $\gamma _{sR}^k(G) \ge \rho (G)\left( k+\delta (G)+1\right) -n(G) = tk$. Consequently, $\gamma _{sR}^k(G) = \rho (G)\left( k+\delta (G)+1\right) -n(G) = tk$. Thus there is an infinite family of graphs achieving equality in Theorem 11.

Corollary 12

If $G$ is a graph of order $n$ with $\delta (G)\ge k-1$, then

$$\begin{aligned} \gamma _{sR}^k(G)\ge \left( 1+\left\lfloor \frac{\mathrm{diam}(G)}{3}\right\rfloor \right) \left( k+\delta (G)+1\right) -n. \end{aligned}$$

Proof

Let $d=\mathrm{diam}(G)=3t+r$ with integers $t\ge 0$ and $0\le r\le 2$, and let $x_0x_1\ldots x_d$ be a diametral path. Then $A=\{x_0,x_3,\ldots ,x_{3t}\}$ is a 2-packing of $G$ such that $|A|=1+\lfloor d/3\rfloor$. Since $\rho (G)\ge |A|$, Theorem 11 implies that

$$\begin{aligned} \gamma _{sR}^k(G)\ge \rho (G)(k+\delta (G)+1)-n\ge \left( 1+\left\lfloor \frac{\mathrm{diam}(G)}{3}\right\rfloor \right) \left( k+\delta (G)+1\right) -n, \end{aligned}$$

and the proof is complete. $\square$

Next we present a so called Nordhaus-Gaddum type inequality for the Roman $k$-domination number of regular graphs.

Theorem 13

If $G$ is an $r$-regular graph of order $n$ such that $r\ge k-1$ and $n-r-1\ge k-1$, then

$$\begin{aligned} \gamma _{sR}^k(G)+\gamma _{sR}^k(\overline{G})\ge \frac{4kn}{n+1}. \end{aligned}$$

If $n$ is even, then $\gamma _{sR}^k(G)+\gamma _{sR}^k(\overline{G})\ge 4k(n+1)/(n+2)$.

Proof

Since $G$ is $r$-regular, the complement $\overline{G}$ is $(n-r-1)$-regular. Therefore it follows from Corollary 4 that

$$\begin{aligned} \gamma _{sR}^k(G)+\gamma _{sR}^k(\overline{G})\ge kn\left( \frac{1}{r+1}+\frac{1}{n-r}\right) \!. \end{aligned}$$

The conditions $r\ge k-1$ and $n-r-1\ge k-1$ imply that $k-1\le r\le n-k$. As the function $g(x)=1/(x+1)+1/(n-x)$ has its minimum for $x=(n-1)/2$ when $k-1\le x\le n-k$, we obtain

$$\begin{aligned} \gamma _{sR}^k(G)+\gamma _{sR}^k(\overline{G})\ge kn\left( \frac{1}{r+1}+\frac{1}{n-r}\right) \ge kn\left( \frac{2}{n+1}+\frac{2}{n+1}\right) =\frac{4kn}{n+1}, \end{aligned}$$

and this is the desired bound. If $n$ is even, then the function $g$ has its minimum for $r=x=(n-2)/2$ or $r=x=n/2$, since $r$ is an integer. Hence this case leads to

$$\begin{aligned} \gamma _{sR}^k(G)+\gamma _{sR}^k(\overline{G})\ge kn\left( \frac{1}{r+1}+\frac{1}{n-r}\right) \ge kn\left( \frac{2}{n}+\frac{2}{n+2}\right) =\frac{4k(n+1)}{n+2}, \end{aligned}$$

and the proof is complete. $\square$

Let $k\ge 1$ be an odd integer, and let $H$ and $\overline{H}$ be $(k-1)$-regular graphs of order $n=2k-1$. By Example 5, we have $\gamma _{sR}^k(H)=\gamma _{sR}^k(\overline{H})=n$. Consequently,

$$\begin{aligned} \gamma _{sR}^k(H)+\gamma _{sR}^k(\overline{H})=2n=\frac{4kn}{n+1}. \end{aligned}$$

Thus the Nordhaus-Gaddum bound of Theorem 13 is sharp for odd $k$.

4 The signed Roman $k$-Domination Number of $K_{p,p}$

Example 14

If $k\ge 1$ and $p\ge k+2$ are integers, then $\gamma _{sR}^k(K_{p,p})=2k+2$.

Proof

Let $X$ and $Y$ be a bipartition of the complete bipartite graph $K_{p,p}$.

First we show that $\gamma _{sR}^k(K_{p,p})\ge 2k+2$. Let $f:V\left( K_{p,p})\right) \longrightarrow \{-1,1,2\}$ be an SRkDF. If $f(u)\ge 1$ for each $u\in V(K_{p,p})$, then $\omega (f)\ge 2p\ge 2k+2$. Assume next, without loss of generality, that $f(x)=-1$ for at least one vertex $x\in X$ and $f(y)\ge 1$ for each $y\in Y$. Then $f(u)=2$ for at least one vertex $u\in Y$. If $w\in Y$ with $w\ne u$, then it follows that

$$\begin{aligned} \omega (f)=f[w]+\sum _{y\in Y-\{w\}}f(y)\ge k+2+p-2\ge 2k+2. \end{aligned}$$

Finally, assume that $f(x)=-1$ for at least one vertex $x\in X$ and $f(y)=-1$ for at least one vertex $y\in Y$. In addition, assume that $f$ assigns $a_1$ vertices in $X$ the value $-$1, $a_2$ vertices in $X$ the value 2, and to the remaining $p-a_1-a_2$ vertices of $X$ the value 1. Further assume that $f$ assigns $b_1$ vertices in $Y$ the value $-$1, $b_2$ vertices in $Y$ the value 2, and to the remaining $p-b_1-b_2$ vertices of $Y$ the value 1. Then $f[x]=-1-b_1+2b_2+p-b_1-b_2\ge k$ and thus $p+b_2-2b_1\ge k+1$. Analogously, $f[y]=-1-a_1+2a_2+p-a_1-a_2\ge k$ and thus $p+a_2-2a_1\ge k+1$. We conclude that

$$\begin{aligned} \omega (f)&= (-a_1+2a_2+p-a_1-a_2)+(-b_1+2b_2+p-b_1-b_2)\\&= (p+a_2-2a_1)+(p+b_2-2b_1)\ge 2k+2. \end{aligned}$$

Since we have discussed all possible case, we obtain $\gamma _{sR}^k(K_{p,p})\ge 2k+2$.

For the converse inequality $\gamma _{sR}^k(K_{p,p})\le 2k+2$, we distinguish two cases.

Case 1. Assume that $p-k$ is even. Let the function $f:V(K_{p,p})\longrightarrow \{-1,1,2\}$ assign to one vertex of $X$ and $Y$ the value 2, to $(p+k-2)/2$ vertices of $X$ and $Y$ the value 1 and to $(p-k)/2$ vertices of $X$ and $Y$ the value $-$1. Then $f$ is an SRkDF on $K_{p,p}$ of weight $\omega (f)=2k+2$ and so $\gamma _{sR}^k(K_{p,p})\le 2k+2$.

Case 2. Assume that $p-k$ is odd. Let the function $f:V(K_{p,p})\longrightarrow \{-1,1,2\}$ assign to two vertices of $X$ and $Y$ the value 2, to $(p+k-5)/2$ vertices of $X$ and $Y$ the value 1 and to $(p-k+1)/2$ vertices of $X$ and $Y$ the value $-$1. Then $f$ is an SRkDF on $K_{p,p}$ of weight $\omega (f)=2k+2$ and so $\gamma _{sR}^k(K_{p,p})\le 2k+2$.

These functions demonstrate that $\gamma _{sR}^k(K_{p,p})\le 2k+2$ and consequently, $\gamma _{sR}^k(K_{p,p})=2k+2$. $\square$

For completenes we determine the signed Roman $k$-domination number of the complete bipartite graph $K_{p,p}$ for $k-1\le p\le k+1$.

Example 15

Let $k\ge 1$ and $k-1\le p\le k+1$ be integers.

• (a) If $k\ge 2$, then $\gamma _{sR}^k(K_{k-1,k-1})=2k-2$.

• (b) $\gamma _{sR}^1(K_{1,1})=1$ and if $k\ge 2$, then $\gamma _{sR}^k(K_{k,k})=2k$.

• (c) $\gamma _{sR}^k(K_{k+1,k+1})=2k+1$.

Proof

• (a) Example 5 leads to $\gamma _{sR}^k(K_{k-1,k-1})=2k-2$ immediately.

• (b) Clearly, $\gamma _{sR}^1(K_{1,1})=1$. Let now $k\ge 2$. By the first part of the proof of Example 14, we conclude that $\gamma _{sR}^k(K_{k,k})\ge 2k$. Applying Theorem 3, we obtain $\gamma _{sR}^k(K_{k,k})=2k$.

• (c) By the first part of the proof of Example 14, we conclude that $\gamma _{sR}^k(K_{k+1,k+1})\ge 2k+1$. If $K_{k+1,k+1}$ has the bipartition $X$ and $Y$, then let the function $f:V(K_{k+1,k+1})\longrightarrow \{-1,1,2\}$ assign to one vertex of $X$ the value $-$1 and to one vertex of $Y$ the value 2 and to all other vertices the value 1. Then it is easy to verify that $f$ is an SRkDF on $K_{k+1,k+1}$ of weight $2k+1$ and so $\gamma _{sR}^k(K_{k+1,k+1})\le 2k+1$. This implies $\gamma _{sR}^k(K_{k+1,k+1})=2k+1$.

$\square$

5 Cycles and Cubic Graphs

As an immediate consequence of Theorem 3 and Corollary 4, we have that for $n \ge 3$, $\gamma _{sR}^3(C_n)=n$ where $C_n$ denotes a cycle on $n$ vertices. The following result establishes the signed Roman $2$-domination number of a cycle.

Example 16

For $n \ge 3$, we have $\displaystyle {\gamma _{sR}^2(C_n)=\left\lceil \frac{2n}{3}\right\rceil +\left\lceil \frac{n}{3}\right\rceil -\left\lfloor \frac{n}{3}\right\rfloor .}$

Proof

Case 1. Assume that $n=3t$ with an integer $t\ge 1$. In view of Corollary 4, we have $\gamma _{sR}^2(C_{3t})\ge 2t$.

Let $C_{3t}=v_0v_1\ldots v_{3t-1}v_0$. Define the function $f:V(C_{3t})\longrightarrow \{-1,1,2\}$ by $f(v_{3i})=-1$, $f(v_{3i+1})=1$ and $f(v_{3i+2})=2$ for $0\le i\le t-1$. Then $f[v_j]=2$ for each $0\le j\le 3t-1$ and therefore $f$ is an SR2DF on $C_{3t}$ of weight $\omega (f)=2t$. Thus $\gamma _{sR}^2(C_{3t})\le 2t$. Consequently, $\gamma _{sR}^2(C_n) = 2t = \left\lceil \frac{2n}{3}\right\rceil +\left\lceil \frac{n}{3}\right\rceil -\left\lfloor \frac{n}{3}\right\rfloor$ in that case.

Case 2. Assume that $n=3t+1$ with an integer $t\ge 1$. Let $C_{3t+1}=v_1v_2\ldots v_{3t+1}v_1$.

Define the function $f:V(C_{3t+1})\longrightarrow \{-1,1,2\}$ by $f(v_{3i})=1$, $f(v_{3i-1})=-1$, $f(v_{3i-2})=2$ for $1\le i\le t$ and $f(v_{3t+1})=2$. Then $f[v_j]\ge 2$ for each $1\le j\le 3t+1$ and therefore $f$ is an SR2DF on $C_{3t+1}$ of weight $\omega (f)=2t+2$. Thus, $\gamma _{sR}^2(C_{3t+1})\le 2t+2$.

Now we show that $\gamma _{sR}^2(C_{3t+1})\ge 2t+2$. Let $f$ be a $\gamma _{sR}^2(C_{3t+1})$-function. If $f(v) = 1$ for all vertices $v \in V(C_{3t+1})$, then $\omega (f) = n \ge 2t+2$. Hence we may assume that $f(v) = 2$ for some vertex $v \in V(C_{3t+1})$. Renaming vertices if necessary, we may assume, without loss of generality, that $f(v_1) = 2$. Then,

$$\begin{aligned} \omega (f) = f(v_{1}) + \sum _{i=1}^{t}f[v_{3i}] \ge 2 + 2t. \end{aligned}$$

Thus $\gamma _{sR}^2(C_{3t+1}) = \omega (f) \ge 2t+2$. Consequently, $\gamma _{sR}^2(C_n) = 2t+2 = \left\lceil \frac{2n}{3}\right\rceil +\left\lceil \frac{n}{3}\right\rceil -\left\lfloor \frac{n}{3}\right\rfloor$ also in that case.

Case 3. Assume that $n=3t+2$ with an integer $t\ge 1$. Let $C_{3t+2}=v_1v_2\ldots v_{3t+2}v_1$.

Define the function $f:V(C_{3t+2})\longrightarrow \{-1,1,2\}$ by $f(v_{3i})=1$, $f(v_{3i-1})=-1$, $f(v_{3i-2})=2$ for $1\le i\le t$, $f(v_{3t+1})=2$ and $f(v_{3t+2})=1$. Then $f[v_j]\ge 2$ for each $1\le j\le 3t+1$ and therefore $f$ is an SR2DF on $C_{3t+2}$ of weight $\omega (f)=2t+3$. Thus $\gamma _{sR}^2(C_{3t+2})\le 2t+3$.

Next we show that $\gamma _{sR}^2(C_{3t+2})\ge 2t+3$. Let $f$ be a $\gamma _{sR}^2(C_{3t+2})$-function. If $f(v) = 1$ for all vertices $v \in V(C_{3t+2})$, then $\omega (f) = n \ge 2t+3$. Hence we may assume that $f(v) = 2$ for some vertex $v \in V(C_{3t+2})$. Renaming vertices if necessary, we may assume, without loss of generality, that $f(v_1) = 2$. Since $f[v_1] \ge 2$, at least one of $v_2$ and $v_{3t+2}$ has a positive weight under $f$. Renaming vertices if necessary, we may assume that $f(v_2) \ge 1$. Then,

$$\begin{aligned} \omega (f) = f(v_{1}) + f(v_2) + \sum _{i=1}^{t}f\left[ v_{3i+1}\right] \ge 2 + 1 + 2t = 2t + 3. \end{aligned}$$

Thus, $\gamma _{sR}^2(C_{3t+2}) = \omega (f) \ge 2t+3$. Consequently, $\gamma _{sR}^2(C_n) = 2t+3 = \left\lceil \frac{2n}{3}\right\rceil +\left\lceil \frac{n}{3}\right\rceil -\left\lfloor \frac{n}{3}\right\rfloor$ also in the last case. $\square$

Next we establish lower and upper bounds on $\gamma _{sR}^k(G)$, when $G$ is a cubic graph and $k \in \{2,3\}$. We shall need the following result due to Favaron [3].

Theorem 17

([3]) If $G$ is a connected cubic graph $G$ of order $n$, then $\rho (G) \ge n/8$, unless $G$ is the Petersen graph in which case $\rho (G) = (n-2)/8 = 1$.

Theorem 18

Let $G$ be a connected cubic graph of order $n$. Then the following holds.

• (a) $\frac{n}{2} \le \gamma _{sR}^2(G) \le \frac{7n}{8}$.

• (b) $\frac{3n}{4} \le \gamma _{sR}^3(G) \le n$.

Proof

The lower bounds follow from Corollary 4. The trivial upper bound in Part (b) follows from Theorem 3. To prove the upper bound in Part (a), let $G$ be a connected cubic graph of order $n$. Let $S$ be a maximum $2$-packing in $G$, and so $|S| = \rho (G)$. If $G$ is the Petersen graph, then $n = 10$ and $\rho (G) = 1$. In this case, let $S = \{v\}$ and let the function $f :V(G) \longrightarrow \{-1,1,2\}$ assign the value $2$ to $v$ and one of its neighbors, the value $-1$ to the two other neighbors of $v$, and the value $1$ to the remaining six vertices of $G$. Then, $f$ is an SR2DF on $G$ of weight $\omega (f) = 8 = 4n/5$, implying that $\gamma _{sR}^2(G) \le 4n/5$. Suppose that $G$ is not the Petersen graph. For each vertex $v \in S$, select one neighbor $v'$ of $v$ and let $S' = \bigcup _{v \in S} \{v'\}$. Since $S$ is a $2$-packing, the sets $S$ and $S'$ are vertex-disjoint and $|S| = |S'| = \rho (G)$. Let the function $f :V(G) \longrightarrow \{-1,1,2\}$ assign to each vertex of $S$ the value $-1$, to each vertex of $S'$ the value $2$ and to all remaining vertices the value $1$. For each vertex $v \in V(G)$, we have that $|N[v] \cap S| \le 1$, implying that $f[v] \ge 3 - 1 = 2$. Thus, $f$ is an SR2DF on $G$ of weight $\omega (f) = 2|S'| + \left( n - |S| - |S'|\right) - |S| = n - 2|S| + |S'| = n - |S| = n - \rho (G)$. By Theorem 17, $\rho (G) \ge n/8$. Hence, $\omega (f) = n - \rho (G) \le n - n/8 = 7n/8$.

That the lower bound of Theorem 18 (a) is tight may be seen by taking a cycle $v_1v_2 \ldots v_{3t}$, where $t \ge 1$, and adding $t$ new vertices $w_1,w_2, \ldots , w_t$ and joining $w_i$ to the three vertices $v_{3i-2},v_{3i-1},v_{3i}$ for $i = 1,2,\ldots ,t$. Let $G$ denote the resulting cubic graph of order $n = 4t$. Assigning the value $-1$ to each vertex $w_i$ and to each vertex $v_{3i-2}$ for all $i$, where $1 \le i \le t$, and assigning the value $2$ to the remaining $2t$ vertices produces an SR2DF on $G$ of weight $2t = n/2$ and so $\gamma _{sR}^2(G) \le n/2$. By Corollary 4, we have that $\gamma _{sR}^2(G) \ge n/2$. Consequently, $\gamma _{sR}^2(G) = n/2$.

That the lower bound of Theorem 18 (b) is tight may be seen by taking a cycle $v_1v_2 \ldots v_{3t}$, where $t \ge 1$, and adding $t$ new vertices $w_1,w_2, \ldots , w_t$ and joining $w_i$ to the three vertices $v_{3i-2}, v_{3i-1},v_{3i}$ for $i = 1,2,\ldots ,t$. Let $G$ denote the resulting cubic graph of order $n = 4t$. Assigning to each vertex $w_i$ the value $-1$, and to each vertex $v_{3i-1}$ where $1 \le i \le t$ the value $2$, and to the remaining $n/2$ vertices the value $1$, we produce an SR3DF on $G$ of weight $3t = 3n/4$ and so $\gamma _{sR}^3(G) \le 3n/4$. By Corollary 4, we have that $\gamma _{sR}^3(G) \ge 3n/4$. Consequently, $\gamma _{sR}^k(G) = 3n/4$.

The upper bound of Corollary 18 (b) is achieved, for example, by the Petersen graph. However we believe the upper bound of Corollary 18 (a) is not best possible and pose the following question.

Question 1

Is it true that if $G$ is a cubic graph of order $n$, then $\gamma _{sR}^2(G) \le 5n/6$.

If Question 1 is true, then the bound is achieved, for example, by $K_{3,3}$ and the prism $K_3 \, \Box K_2$.

In a graph $G$, a vertex dominates itself and its neighbors. Harary and Haynes [5] defined a subset $S \subseteq V(G)$ to be a double dominating set, abbreviated DD-set, of $G$ if $S$ dominates every vertex of $G$ at least twice; that is, $v$ is in $S$ and has at least one neighbor in $S$ or $v$ is in $V-S$ and has at least two neighbors in $S$. The double domination number, $\gamma _{\times 2}(G)$, of $G$ is the minimum cardinality of a DD-set in $G$. A DD-set of cardinality $\gamma _{\times 2}(G)$ is called a $\gamma _{\times 2}(G)$-set. Let $G$ be a cubic graph of order $n$, and let $S$ be a $\gamma _{\times 2}(G)$-set. Assigning to each vertex in $S$ the value $2$, and to each vertex in $V - S$ the value $-1$, we produce an SR2DF on $G$ of weight $2|S| - (n - |S|) = 3|S| - n = 3\gamma _{\times 2}(G) - n$, implying that $\gamma _{sR}^2(G) \le 3\gamma _{\times 2}(G) - n$. Hence we have the following observation.

Observation 19

If $G$ is a cubic graph of order $n$, then $\gamma _{sR}^2(G) \le 3\gamma _{\times 2}(G) - n$.

6 Trees

Our aim in the section is to determine $\gamma _{sR}^2(P_n)$ for the path $P_n$ and to establish a lower bound on the signed Roman $2$-domination number of a tree in terms of its order. As illustrated in Example 10, there are connected graphs whose signed Roman $2$-domination number is negative. We show that this is not the case for the class of trees. We begin with the following observation.

Observation 20

Let $T$ be a tree of order $n$ and let $f$ be an SR2DF on $T$. Then the following holds.

• (a) If $v$ is a leaf or a support vertex in $T$, then $f(v) \ge 1$.

• (b) If $2 \le n \le 5$, then $\gamma _{sR}^2(T) = n$.

• (c) If $6 \le n \le 7$ and $T = P_n$, then $\gamma _{sR}^2(P_n) = n$.

By Observation 20, if $P_n$ is a path of order $2 \le n\le 7$, then $\gamma _{sR}^2(P_n)=n$.

Example 21

For $n \ge 8$, we have $\gamma _{sR}^2(P_n)=\left\lceil \frac{2n+5}{3}\right\rceil$.

Proof

Let $P_n \!=\! v_0v_1\ldots v_{n-1}$. By Observation 20, we note that $f(v_0),f(v_1),f(v_{n-2}),f(v_{n-1})\ge 1$.

Case 1. Assume that $n=3t+2$ with an integer $t\ge 2$. Define the function $f:V(P_{3t+2})\longrightarrow \{-1,1,2\}$ by $f(v_{3i})=1$, $f(v_{3i+1})=2$ for $0\le i\le t$ and $f(v_{3i+2})=-1$ for $0\le i\le t-1$. Then $f[v_j]\ge 2$ for each $0\le j\le 3t+1$ and therefore $f$ is an SR2DF on $P_{3t+2}$ of weight $\omega (f)=2t+3$. Thus $\gamma _{sR}^2(P_{3t+2})\le 2t+3$.

Next we show that $\gamma _{sR}^2(P_{3t+2})\ge 2t+3$. Let $f$ be a $\gamma _{sR}^2(P_{3t+2})$-function. If $f(v_2) \ge 1$, then

$$\begin{aligned} \omega (f)&= f(v_0)+f(v_{1}) + f(v_2) + \left( \sum \nolimits _{i=1}^{t-1}f\left[ v_{3i+1}\right] \right) \nonumber \\&+f(v_{3t})+f(v_{3t+1})\ge 3+2(t-1)+2=2t+3. \end{aligned}$$

If $f(v_2)=-1$, then $f(v_0)+f(v_1)\ge 3$ and so

$$\begin{aligned} \omega (f) = f(v_0)+f(v_{1}) + \sum _{i=1}^{t}f[v_{3i}]\ge 3+2t. \end{aligned}$$

Thus $\gamma _{sR}^2(P_{3t+2}) = \omega (f) \ge 2t+3$. Consequently, $\gamma _{sR}^2(P_n) = 2t+3 = \left\lceil \frac{2n+5}{3}\right\rceil$ in that case.

Case 2. Assume that $n=3t$ with an integer $t\ge 3$. Define the function $f:V(P_{3t})\longrightarrow \{-1,1,2\}$ by $f(v_{3i})=1$, $f(v_{3i+1})=2$ for $0\le i\le t-1$, $f(v_{3i+2})=-1$ for $0\le i\le t-2$ and $f(v_{3t-1})=1$. Then $f[v_j]\ge 2$ for each $0\le j\le 3t-1$ and therefore $f$ is an SR2DF on $P_{3t}$ of weight $\omega (f)=2t+2$. Thus $\gamma _{sR}^2(P_{3t})\le 2t+2$.

Next we show that $\gamma _{sR}^2(P_{3t})\ge 2t+2$. Let $f$ be a $\gamma _{sR}^2(P_{3t})$-function. If $f(v_2)=2$, then

$$\begin{aligned} \omega (f) = f(v_0)+f(v_{1}) + f(v_2) + \sum _{i=1}^{t-1}f[v_{3i+1}]\ge 4+2(t-1) =2t+2. \end{aligned}$$

If $f(v_2)=1$ and $f(v_3)\ge 1$, then

$$\begin{aligned} \omega (f)&= f(v_0)+f(v_{1}) + f(v_2) + f(v_3)+ \left( \sum _{i=1}^{t-2}f\left[ v_{3i+2}\right] \right) \nonumber \\ \qquad&+f(v_{3t-2})+f(v_{3t-1})\ge 6+2(t-2)=2t+2. \end{aligned}$$

If $f(v_2)=1$ and $f(v_3)=-1$, then $f(v_1)=2$ and so

$$\begin{aligned} \omega (f) = f(v_0)+f(v_{1})+f(v_2) + \sum _{i=1}^{t-1}f\left[ v_{3i+1}\right] \ge 4+2(t-1)=2t+2. \end{aligned}$$

If $f(v_2)=-1$, then $f(v_0)+f(v_1)\ge 3$ and hence

$$\begin{aligned} \omega (f) = f(v_0)+f(v_{1})+ \left( \sum _{i=1}^{t-1}f\left[ v_{3i}\right] \right) +f(v_{3t-1})\ge 4+2(t-1)=2t+2. \end{aligned}$$

Thus $\gamma _{sR}^2(P_{3t}) = \omega (f) \ge 2t+2$. Consequently, $\gamma _{sR}^2(P_n) = 2t+2 = \left\lceil \frac{2n+5}{3}\right\rceil$ also in that case.

Case 3. Assume that $n=3t+1$ with an integer $t\ge 3$. Define the function $f:V(P_{3t+1})\longrightarrow \{-1,1,2\}$ by $f(v_{3i})=1$ for $0\le i\le t$, $f(v_{3t-1})=1$, $f(v_{3i+1})=2$ for $0\le i\le t-1$ and $f(v_{3i+2})=-1$ for $0\le i\le t-2$. Then $f[v_j]\ge 2$ for each $0\le j\le 3t$ and therefore $f$ is an SR2DF on $P_{3t+1}$ of weight $\omega (f)=2t+3$. Thus $\gamma _{sR}^2(P_{3t+1})\le 2t+3$.

Next we show that $\gamma _{sR}^2(P_{3t+1})\ge 2t+3$. Let $f$ be a $\gamma _{sR}^2(P_{3t})$-function. If $f(v_2)=2$, then

$$\begin{aligned} \omega (f)&= f(v_0)+f(v_{1}) + f(v_2) + \left( \sum _{i=1}^{t-1}f[v_{3i+1}]\right) \nonumber \\&+ f(v_{3t})\ge 5+2(t-1)=2t+3. \end{aligned}$$

Let next $f(v_2)=1$. If $f(v_3)=2$, then

$$\begin{aligned} \omega (f) = f(v_0)+f(v_{1}) + f(v_2) + f(v_3)+\sum _{i=1}^{t-1}f[v_{3i+2}]\ge 5+2(t-1)=2t+3. \end{aligned}$$

If $f(v_3)=1$, then $f(v_4)\ge 1$ and so

$$\begin{aligned} \omega (f)&= f(v_0)+f(v_{1})+f(v_2)+f(v_3)+f(v_4)+ \left( \sum _{i=2}^{t-1}f[v_{3i}] \right) \nonumber \\&+f(v_{3t-1})+f(v_{3t})\ge 7+2(t-2)=2t+3. \end{aligned}$$

If $f(v_3)=-1$, then $f(v_1)=f(v_4)=2$ and hence

$$\begin{aligned} \omega (f)&= f(v_0)+f(v_{1})+f(v_2)+f(v_3)+f(v_4)+ \left( \sum _{i=2}^{t-1}f[v_{3i}] \right) \nonumber \\&+f(v_{3t-1})+f(v_{3t})\ge 7+2(t-2)=2t+3. \end{aligned}$$

Finally, let $f(v_2)=-1$. Then $f(v_0)+f(v_1)\ge 3$ and so

$$\begin{aligned} \omega (f)&= f(v_0)+f(v_{1})+ \left( \sum _{i=1}^{t-1}f[v_{3i}] \right) \nonumber \\&+f(v_{3t-1})+f(v_{3t})\ge 5+2(t-1)=2t+3. \end{aligned}$$

Thus $\gamma _{sR}^2(P_{3t+1}) = \omega (f) \ge 2t+3$. Consequently, $\gamma _{sR}^2(P_n) = 2t+3 = \left\lceil \frac{2n+5}{3}\right\rceil$ also in the last case. $\square$

The next result provided a lower bound on the signed Roman $2$-domination number of a tree in terms of its order.

Theorem 22

If $T$ is a tree of order $n\ge 4$, then

$$\begin{aligned} \gamma _{sR}^2(T)\ge \frac{n+4}{2}. \end{aligned}$$

Proof

We proceed by induction on the order $n \ge 4$. If $n = 4$, then by Observation 20 (b), $\gamma _{sR}^2(T) = n = (n+4)/2$. This establishes the base case when $n=4$. Let $n \ge 5$ and suppose that if $T'$ is a tree of order $n'$ where $4\le n'<n$, then $\gamma _{sR}^2(T) \ge (n'+4)/2$. Let $T$ be a tree of order $n$. Choose an optimal SR2DF $f$ on $T$, and so $\gamma _{sR}^2(T) = \omega (f)$. If $f(x)\ge 1$ for each vertex $x\in V(T)$, then $\omega (f)\ge n>(n+4)/2$. Now suppose that there is a vertex $v\in V(T)$ with $f(v)=-1$. Suppose that $T-v$ is the disjoint union of $r$ trees $T_1,T_2,\ldots ,T_r$. Let $f_i$ be the restriction of $f$ on $T_i$ for $1\le i\le r$. Clearly, $f_i$ is an SR2DF on $T_i$ for $1\le i\le r$. Since by Observation 20 (a) a leaf and its only neighbor has a positive label, $r\ge 2$ and each $T_i$ has $n_i\ge 2$ vertices. If $n_i=2$, then in fact $\omega (f_i)\ge 3=(n_i+4)/2$, and if $n_i=3$, then $\omega (f_i) = 3$ or $\omega (f_i) \ge 4 > (n_i+4)/2$. If $n_i\ge 4$, then by the induction hypothesis $\omega (f_i)\ge (n_i+4)/2$. If $\omega (f_i)\ge (n_i+4)/2$ for all $i$, then since $r \ge 2$,

$$\begin{aligned} \omega (f) = -1 + \sum _{i=1}^r\omega (f_i) \ge -1+\sum _{i=1}^r\frac{n_i+4}{2}= \frac{n + 4r - 3}{2} \ge \frac{n + 5}{2}. \end{aligned}$$

Hence we may assume that for some $i$, $n_i=3$ and $\omega (f_i) = 3$, for otherwise the desired result follows. Assume that $T_1,T_2,\ldots ,T_q$, $q \ge 1$, are exactly the trees with three vertices and with $\omega (f_i) = 3$, $1 \le i \le q$. We note that $f(w) = 1$ for each vertex $w$ that belongs to such a tree $T_i$ with $\omega (f_i) = 3$. Hence since $v$ is adjacent to at least one vertex $w$ with $f(w) = 2$, we have that $r > q$. Thus

$$\begin{aligned} \omega (f)&= -1+\sum _{i=1}^q\omega (f_i)+\sum _{i=q+1}^r\omega (f_i) \\&\ge -1+3q+\sum _{i=q+1}^r\frac{n_i+4}{2}\\&= \frac{n + 4(r-q)+3(q-1)}{2} \\&\ge \frac{n + 4}{2}, \end{aligned}$$

as desired. $\square$