On [k]-Roman domination subdivision number of graphs

Abstract

Let $k\ge 1$ be an integer and G a simple graph with vertex set V(G). Let f be a function that assigns labels from the set $\{0,1,2,\dots ,k+1\}$ to the vertices of G. For a vertex $v\in V(G),$ the active neighbourhood AN(v) of v is the set of all vertices w adjacent to v such that $f(w)\ge 1.$ A [k]-Roman dominating function (or [k]-RDF for short) is a function $f:V(G)\to \{0,1,2,\dots ,k+1\}$ satisfying the condition that for any vertex $v\in V(G)$ with f(v) < k, $f(N[v])\ge |AN(v)|+k.$ The weight of a [k]-RDF is $\omega (f)={\Sigma }_{v\in V(G)}f(v),$ and the [k]-Roman domination number ${\gamma }_{[kR]}(G)$ of G is the minimum weight of an [k]-RDF on G. In this paper we shall be interested in the study of the [k]-Roman domination subdivision number sd${}_{{\gamma }_{[kR]}}(G)$ of G defined as the minimum number of edges that must be subdivided, each once, in order to increase the [k]-Roman domination number. We first show that the decision problem associated with sd${}_{{\gamma }_{[kR]}}(G)$ is NP-hard. Then various properties and bounds are established.

Keywords:

• [k]-Roman domination number
• [k]-Roman domination subdivision number

MSC 2000:

• 05C69

1. Introduction

For notation and graph theory terminology, we in general follow Haynes, Hedeniemi and Slater [16]. Throughout this paper, G denotes a simple graph, with vertex set $V=V(G)$ and edge set $E=E(G).$ The order $|V(G)|$ of G is denoted by $n=n(G).$ The open neighborhood of a vertex v is the set $N(v)=\{u\in V(G)|uv\in E(G)\}$ and the closed neighborhood of a vertex v is the set $N[v]=N(v)\cup \left\{v\right\}.$ The degree of a vertex $v\in V$ is ${\mathrm{deg}}_G(v)=\mathrm{deg}(v)=|N(v)|.$ The minimum and maximum degree of a graph G are denoted by $\delta (G)=\delta$ and $\Delta (G)=\Delta ,$ respectively. The subdivision of an edge uv of a graph G consists of the deletion of uv from G and the addition of two edges ux and xv along with a new vertex x that will be called a subdivision vertex. As usual, K_n, P_n and C_n denote the complete graph, the path and the cycle of order n.

Let $k\ge 1$ be an integer and let f be a function that assigns labels from the set $\{0,1,\dots ,k+1\}$ to the vertices of G. The active neighborhood AN(v) of a vertex $v\in V(G)$ with respect to f is the set of all vertices $w\in N(v)$ such that $f(w)\ge 1.$ A [k]-Roman dominating function on a graph G, abbreviated [k]-RDF, is a function $f:V(G)\to \{0,1,\dots ,k+1\}$ satisfying the condition that for any vertex $v\in V(G)$ with f(v) < k, $f(N[v])\ge |AN(v)|+k.$ The weight of a [k]-RDF is $\omega (f)={\Sigma }_{v\in V(G)}f(v),$ and the [k]-Roman domination number ${\gamma }_{[kR]}(G)$ of G is the minimum weight of a [k]-RDF on G. A ${\gamma }_{[kR]}(G)$-function is a [k]-RDF of weight ${\gamma }_{[kR]}(G).$ Moreover, if f is a [k]-RDF on G, we let $V_i^f=\{v\in V|f(v)=i\}$ for every $i\in \{0,1,\dots ,k+1\}.$ Consequently, any [k]-RDF f can be represented by $f=(V_0^f,V_1^f,\dots ,V_{k+1}^f),$ where the superscript f can be deleted in $V_i^f$ when no confusion arises. The [k]-Roman domination number was introduced by Abdollahzadeh Ahangar at al. in [1] and has been studied by several authors [3, 14, 15, 17, 19, 20]. Note that ${\gamma }_{[1R]}(G)$ coincides with the Roman domination number ${\gamma }_R(G),$ ${\gamma }_{[2R]}(G)$ coincides with the double Roman domination number, ${\gamma }_{[3R]}(G)$ coincides with the triple Roman domination number, while ${\gamma }_{[4R]}(G)$ coincides with the quadruple Roman domination number. For more details on Roman domination and its variations we refer the reader to the two book chapters and surveys papers [8–12].

In this paper we are interested in the study of the [k]-Roman domination subdivision number, abbreviated [k]-RDS-number, sd${}_{{\gamma }_{[kR]}}(G)$ of a graph G defined as the minimum number of edges that must be subdivided, where each edge in G is subdivided at most once, in order to increase the [k]-Roman domination number. It is worth mentioning that the $[1]$-RDS-number matches with the Roman domination subdivision number ${\text{sd}}_{{\gamma }_R}(G)$ which has been studied in [2, 4, 7, 18]. Also, the $[2]$-RDS-number and [3]-RDS-number coincide with the double Roman domination subdivision and triple Roman domination subdivision numbers, respectively, that have been recently investigated in [5, 6].

In this paper, we begin by showing that the decision problem associated with sd${}_{{\gamma }_{[kR]}}(G)$ is NP-hard, and then upper bounds on the [k]-RDS-number are established for arbitrary graphs.

Before further proceeding, it should be noted that since the [k]-RDS-number of the graph K₂ does not change when its only edge is subdivided, we will assume that at least one component of the graph G has order at least 3. Moreover, if $G_1,G_2,\dots ,G_s$ are the components of G then ${\gamma }_{[kR]}(G)={\Sigma }_{i=1}^s{\gamma }_{[kR]}(G_i)$ and if $G_1,G_2,\dots ,G_t$ are the components of G of order at least 3, then ${\text{sd}}_{{\gamma }_{[kR]}}(G)=\min \{{\text{sd}}_{{\gamma }_{[kR]}}(G_i)|1\le i\le t\}.$ Hence, we will only consider connected graphs of order at least three.

We start by showing that the subdivision of any edge does not decrease the [k]-Roman domination number.

Proposition 1.

Let G be a simple connected graph of order $n\ge 3$ and $e=uv\in E(G)$. If $G^{\prime }$ is obtained from G by subdivision the edge e, then ${\gamma }_{[kR]}(G^{\prime })\ge {\gamma }_{[kR]}(G)$ for every integer $k\ge 1.$

Proof.

Let x be the subdivision vertex and let f be a ${\gamma }_{[kR]}(G^{\prime })$-function. Define the function $g:V(G)\to \{0,1,\dots ,k+1\}$ by $g(u)=\min \{k+1,f(u)+f(x)\}$ and $g(z)=f(z)$ for $z\in V(G)\setminus \left\{u\right\}.$ Clearly g is a [k]-RDF on G and $\omega (g)\le \omega (f).$ Hence ${\gamma }_{[kR]}(G^{\prime })\ge {\gamma }_{[kR]}(G)$ as desired.□

We end this section by the following results that are useful to our proofs.

Proposition 2

([17]). If $k\ge 2$, then in a [k]-RDF of weight ${\gamma }_{[kR]}(G)$, no vertex needs to be assigned the value 1.

Observation 3.

Let G be a connected graph of order $n\ge 3.$ Then $${\gamma }_{\left[kR\right]}(G)\ge k+1,$$ with equality if and only if $\Delta (G)=n-1.$

2. NP-hardness result

In this section, we will show that the [k]-Roman domination subdivision number problem, to which we shall refer as [k]-RDSN, is NP-hard even for bipartite graphs.

$[\mathbf{k}]$-Roman domination subdivision number problem ($[\mathbf{k}]$-RDSN):

Instance: A nonempty bipartite graph G and a positive integer $\mathcal{l}.$

Question: Is ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \mathcal{l}$?

Following Garey and Johnson’s techniques for proving NP-completeness given in [13], we prove our result by describing a polynomial transformation from the well-known NP-complete problem 3-SAT to [k]-RDSN. Before stating the 3-SAT problem, let us recall the following.

Let U be a set of Boolean variables. A truth assignment for U is a mapping $t:U\to \{T,F\}.$ If t(u) = T, then u is said to be “true” under t; if t(u) = F, then u is said to be “false” under t. If u is a variable in U, then u and $\overline{u}$ are literals over U. The literal u is true under t if, and only if, the variable $\overline{u}$ is false under t; the literal $\overline{u}$ is true if, and only if, the variable u is false.

A clause over U is a set of literals over U. It represents the disjunction of these literals and is satisfied by a truth assignment if, and only if, at least one of its members is true under that assignment. A collection $\mathcal{C}$ of clauses over U is satisfiable if, and only if, there exists some truth assignment for U that simultaneously satisfies all the clauses in $\mathcal{C}.$ Such a truth assignment is called a satisfying truth assignment for $\mathcal{C}.$ The 3-SAT is specified as follows.

3. Satisfiability problem (3-SAT)

Instance: A collection $\mathcal{C}=\{C_1,C_2,\dots ,C_m\}$ of clauses over a finite set U of variables such that $\left|Cj\right|=3$ for $j=1,2,\dots ,m.$

Question: Is there a truth assignment for U that satisfies all the clauses in $\mathcal{C}$?

Theorem 4

([13] Theorem 3.1). 3-SAT is NP-complete.

Theorem 5.

The [k]-RDSN problem is NP-hard for bipartite graphs for every integer $k\ge 2.$

Proof.

Let $U=\{u_1,u_2,\dots ,u_n\}$ and $\mathcal{C}=\{C_1,C_2,\dots ,C_m\}$ be an arbitrary instance of 3SAT. We will construct a bipartite graph G and choose an integer $\mathcal{l}$ such that $\mathcal{C}$ be satisfiable if and only if ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \mathcal{l}.$ We construct such a bipartite graph G as follows.

For each $i\in \{1,2,\dots ,n\},$ we associate to each variable $u_i\in U,$ a copy of the complete bipartite graph $H_i=K_{3,5}$ with bipartite sets $X=\{x_i,y_i,z_i\}$ and $Y=\{v_i,u_i,w_i,\overline{u_i},r_i\}.$ For each $j\in \{1,2,\dots ,m\},$ we associate to each clause $C_j\in \mathcal{C},$ a single vertex c_j by adding the edges $c_j{u}_i$ if $u_i\in C_j$ and $c_j\overline{u_i}$ if $\overline{u_i}\in C_j.$ Finally, to obtain the graph G, we add a graph H isomorphic to a path $P_{10}:s_1{s}_2\dots s_9{s}_{10}$ by joining each of s₁ and s₁₀ to all c_j’s. Set $\mathcal{l}=1.$

Figure 1 provides an example of the constructed graph when $U=\{u_1,u_2,u_3,u_4\}$ and $\mathcal{C}=\{C_1,C_2,C_3\},$ where $C_1=\{u_1,u_2,\overline{u_3}\},C_2=\{\overline{u_1},u_2,u_4\},C_3=\{\overline{u_2},u_3,u_4\}.$ To prove that this is indeed a transformation, we only need to show that ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1$ if and only if there is a truth assignment for U that satisfies all clauses in $\mathcal{C}.$ This aim will be achieved through the proof of the following four claims.

Figure 1. An instance of the [k]-Roman subdivision number problem resulting from an instance of 3SAT. Here $\mathcal{l}=1$ and ${\gamma }_{[kR]}(G)=12k+11,$ where the bold vertex p means there is a [k]-RDF f with $f(p)=k+1,$ with the exception of s₄ where $f(s_4)=k.$

Claim 1. ${\gamma }_{[kR]}(G)\ge (2n+4)(k+1)-1.$ Moreover, if ${\gamma }_{[kR]}(G)=(2n+4)(k+1)-1,$ then for any ${\gamma }_{[kR]}$-function f on G, $f(V(H_i))=2(k+1),f(s_1)=f(s_{10})=0$ or $\{f(s_1),f(s_2)\}=\{0,k\}$ and $f(c_j)=0$ for each $1\le j\le m.$

Proof

of Claim 1. Let f be a ${\gamma }_{[kR]}$-function of G. Without loss of generality, assume that $f(z)\ne 1$ for all vertex $z\in V(G)$ (by Proposition 2). For each $i\in \{1,2,\dots ,n\},$ it is clear that $f(V(H_i))\ge 2(k+1)$ and $f(V(H))+{\sum }_{i=1}^{m}f(c_j)\ge 4k+3,$ implying that ${\gamma }_{[kR]}(G)\ge (2n+4)(k+1)-1.$ Now suppose that ${\gamma }_{[kR]}(G)=(2n+4)(k+1)-1.$ Since each H_i is isomorphic to $K_{3,5},f(V(H_i))=2(k+1).$ Next, we show that $f(s_1)=f(s_{10})=0$ or $\{f(s_1),f(s_{10})\}=\{0,k\}.$ Suppose for a contradiction that $f(s_1)\ne 0$ or $f(s_{10})\ne 0$ and $\{f(s_1),f(s_{10}\}\ne \{0,k\}.$

If $f(s_1)=k+1$ (the case $f(s_{10})=k+1$ is similar), then since $f(N_G[s_4])\ge k+1,f(N_G[s_7])\ge k+1$ and thus $f(N_G[s_{10}])\ge k+1$ implying that ${\gamma }_{[kR]}(G)=(2n+4)(k+1),$ which leads to a contradiction. Hence let $0<f(s_1)<k$ (the case $0<f(s_{10})<k$ is similar), then $f(N_G[s_1])\ge k+1$ and $f(N_G[s_4])+f(N_G[s_7])+f(s_9)+f(s_{10})\ge 3(k+1),$ implying that ${\gamma }_{[kR]}(G)=(2n+4)(k+1),$ a contradiction. Therefore $f(s_1)=f(s_{10})=0$ or $\{f(s_1),f(s_{10}\}=\{0,k\}.$ It follows that $f(V(H))=4k+3$ and thus ${\sum }_{j=1}^{m}f(c_j)=0,$ as desired.$♦$

Claim 2. $\mathcal{C}$ is satisfiable if and only if ${\gamma }_{kR}(G)=(2n+4)(k+1)-1.$

Proof

of Claim 2. Suppose that ${\gamma }_{[kR]}(G)=(2n+4)(k+1)-1$ and let f be a ${\gamma }_{[kR]}$-function of G that assigns no 1 to any vertex of G. By Claim 1, $f(V(H_i))=2(k+1)$ for each $i\in \{1,2,\dots .n\},$ and since H_i is a complete bipartite graph, at most one of $f(u_i)$ and $f(\overline{u_i})$ is assigned k + 1 for each i. Define the mapping $t:U\to \{T,F\}$ by (1) $$t(u_i)=\{\begin{array}{cc}T\hfill & \text{if either f}({\mathrm{u}}_{\mathrm{i}})=\mathrm{k}+1\mathrm{ }\text{or}\mathrm{ }\mathrm{f}({\mathrm{u}}_{\mathrm{i}})\ne \mathrm{k}+1\mathrm{ }\text{and}\mathrm{ }\mathrm{f}({\overline{u}}_{\mathrm{i}})\ne \mathrm{k}+1\hfill \\ F\hfill & \text{if f}(\overline{{\mathrm{u}}_{\mathrm{i}}})=\mathrm{k}+1,\hfill \end{array}$$(1) for each $i\in \{1,\dots ,n\}.$ We now show that t is a satisfying truth assignment for $\mathcal{C}.$ It is sufficient to show that every clause in $\mathcal{C}$ is satisfied by t. To this end, we arbitrarily choose a clause $C_j\in \mathcal{C}$ for some $j\in \{1,\dots ,m\}.$

By Claim 1, since $f(s_1)+f(s_{10})<k+1$ and $c_j{s}_h\notin E(G)$ for every $h\in \{2,\dots ,9\},$ there exists some index i with $i\in \{1,\dots ,n\}$ such that c_j is adjacent to u_i or $\overline{u_i}.$ Suppose that c_j is adjacent to u_i where $f(u_i)=k+1.$ Since u_i is adjacent to c_j in G, the literal u_i is in the clause C_j by the construction of G. Since $f(u_i)=k+1,$ it follows that $t(u_i)=T$ by (1), which implies that the clause C_j is satisfied by t. Suppose that c_j is adjacent to $\overline{u_i}$ where $f(\overline{u_i})=k+1.$ Since $\overline{u_i}$ is adjacent to c_j in G, the literal $\overline{u_i}$ is in the clause C_j. Since $f(\overline{u_i})=k+1,$ it follows that $t(u_i)=F$ by (1). Thus, t assigns $\overline{u_i}$ the truth value T, that is, t satisfies the clause C_j. By the arbitrariness of j, we conclude that t satisfies all the clauses in $\mathcal{C},$ so $\mathcal{C}$ is satisfiable.

Conversely, suppose that $\mathcal{C}$ is satisfiable, and let $t:U\to \{T,F\}$ be a satisfying truth assignment for $\mathcal{C}.$ Create a function f on V(G) as follows: if $t(u_i)=T,$ then let $f(u_i)=k+1,$ and if $t(u_i)=F,$ then let $f(\overline{u_i})=k+1.$ Let $f(y_i)=k+1$ for each i, $f(s_2)=f(s_6)=f(s_9)=k+1,f(s_4)=k,$ and the remaining vertices of G are assigned a 0 under f. Clearly, $f(G)=(2n+4)(k+1)-1.$ Since t is a satisfying truth assignment for $\mathcal{C},$ for each $j\in \{1,2,\dots ,m\},$ at least one of literals in C_j is true under the assignment t. It follows that the corresponding vertex c_j in G is adjacent to at least one vertex p with $f(p)=k+1.$ Since c_j is adjacent to each literal in C_j by the construction of G, thus f is a [k]-RDF of G, and so ${\gamma }_{[kR]}(G)\le f(G)=(2n+4)(k+1)-1.$ By Claim 1, ${\gamma }_{[kR]}(G)\ge (2n+4)(k+1)-1,$ and thus ${\gamma }_{[kR]}(G)=(2n+4)(k+1)-1.$$♦$

Claim 3. Let $G^{\prime }$ be obtained from G by subdividing any edge e of E(G), then ${\gamma }_{[kR]}(G^{\prime })\le (2n+4)(k+1).$

Proof

of Claim 3. Let $e=uv\in E(G)$ and let $G^{\prime }$ be obtained from G by subdividing the edge e. Consider the following cases:

Case 1.

$e=s_i{s}_{i+1}$ for some $i\in \{1,\dots ,9\}.$

Without loss of generality, let $e=s_1{s}_2$ and define the function f on $V(G^{\prime })$ by $f(s_1)=f(s_3)=f(s_6)=f(s_9)=f(x_i)=f(v_i)=k+1$ for each $1\le i\le n$ and f(x) = 0 for all other $x\in V(G^{\prime }).$

Case 2.

$e\in \{s_1{c}_j,s_{10}{c}_j\},$ for some $j\in \{1,\dots ,m\}.$

Consider the function f defined on $V(G^{\prime })$ by $f(s_1)=f(s_4)=f(s_7)=f(s_{10})=f(x_i)=f(v_i)=k+1$ for each $1\le i\le n$ and f(x) = 0 for all other $x\in V(G^{\prime }).$

Case 3.

$e=c_j{u}_i,$ for some $i\in \{1,\dots ,n\}$ and some $j\in \{1,\dots ,m\}$ or $e=c_j{\overline{u}}_i,$ for some $i\in \{1,\dots ,n\}$ and some $j\in \{1,\dots ,m\}.$

Consider the function f defined on $V(G^{\prime })$ by $f(s_1)=f(s_4)=f(s_7)=f(s_9)=f(x_i)=f(u_i)=k+1$ or $f(s_1)=f(s_4)=f(s_7)=f(s_9)=f(x_i)=f(\overline{u_i})=k+1$ respectively, for each $i\in \{1,\dots ,n\}$ and f(x) = 0 for all other $x\in V(G^{\prime }).$

Case 4.

e = uv where $u\in \{x_i,y_i,z_i\}$ and $v\in \{v_i,u_i,w_i,{\overline{u}}_i,r_i\}.$

Consider the function f defined on $V(G^{\prime })$ by $f(s_1)=f(s_4)=f(s_7)=f(s_9)=f(u)=f(v)=k+1$ and f(x) = 0 for all other $x\in V(G^{\prime }).$

In either case, f is a [k]-RDF on $G^{\prime }$ of weight $(2n+4)(k+1),$ and therefore ${\gamma }_{[kR]}(G^{\prime })\le (2n+4)(k+1).$$♦$

Claim 4. ${\gamma }_{[kR]}(G)=(2n+4)(k+1)-1$ if and only if ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1.$

Proof

of Claim 4. Assume ${\gamma }_{[kR]}(G)=(2n+4)(k+1)-1,$ and let $G^{\prime }$ be the graph obtained from G by subdivision the edge $e=s_1{s}_2$ with vertex subdivision w.

Suppose for a contradiction that ${\gamma }_{[kR]}(G)={\gamma }_{[kR]}(G^{\prime }),$ and let $f^{\prime }$ be a ${\gamma }_{[kR]}(G^{\prime })$-function. Define the function g on V(G) by $g(s_1)=\min \{f^{\prime }(s_1)+f^{\prime }(w),k+1\}$ and $g(z)=f^{\prime }(z)$ for $z\in V(G)\setminus \left\{s_1\right\}.$ Clearly, g is a [k]-RDF of G and thus ${\gamma }_{[kR]}(G)\le \omega (g)\le \omega (f^{\prime })={\gamma }_{[kR]}(G^{\prime }),$ implying that ${\gamma }_{[kR]}(G)=\omega (g)$ and g is a ${\gamma }_{[kR]}(G)$-function on G. By Claim 1, $g(s_1)=0$ or $g(s_1)=k.$ If $g(s_1)=0,$ then $f^{\prime }(s_1)+f^{\prime }(w)=0$ and so $f^{\prime }(s_1)=f^{\prime }(w)=0.$ It follows that ${\sum }_{j=1}^m{f}^{\prime }(c_j)\ne 0,$ and since $g(z)=f^{\prime }(z)$ for $z\in V(G)\setminus \left\{s_1\right\},$ we deduce that ${\sum }_{j=1}^{m}g(c_j)\ne 0,$ which leads to a contradiction (with Claim 1). If $g(s_1)=k,$ then $f^{\prime }(s_1)+f^{\prime }(w)=k,$ and since $f^{\prime }(s_1)+f^{\prime }(w)+{\sum }_{j=1}^m{f}^{\prime }(c_j)\ge k+1,$ we deduce that ${\sum }_{j=1}^m{f}^{\prime }(c_j)\ne 0,$ yielding as above to the contradiction ${\sum }_{j=1}^{m}g(c_j)\ne 0.$ Therefore, ${\gamma }_{[kR]}(G)<{\gamma }_{[kR]}(G^{\prime }),$ and thus ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1.$

Now, assume that ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1,$ and let $G^{\prime }$ be the graph obtained from G by subdividing the edge e for which ${\gamma }_{[kR]}(G)<{\gamma }_{[kR]}(G^{\prime }).$ By Claim 3, we have ${\gamma }_{[kR]}(G^{\prime })\le (2n+4)(k+1).$ It follows from Claim 1 that $$(2n+4)(k+1)-1\le {\gamma }_{\left[kR\right]}(G)<{\gamma }_{\left[kR\right]}(G^{\prime })\le (2n+4)(k+1),$$ and thus ${\gamma }_{[kR]}(G)=(2n+4)(k+1)-1,$ as desired.$♦$

By Claims 2 and 4, we showed that ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1$ if and only if there is a truth assignment for U that satisfies all clauses in $\mathcal{C}.$ Since the construction of the [k]-RDSN instance is straightforward from a 3-satisfiability instance, the size of the [k]-RDSN instance is bounded above by a polynomial function of the size of 3-satisfiability instance. It follows that this is a polynomial reduction and the proof is complete.□

4. Bounds on the [k]-RDS-number

In this section we present some sufficient conditions for graphs to have small [k]-RDS-number. Recall that a vertex of degree one is called a leaf and its neighbor a support vertex.

Proposition 6.

If G contains a support vertex with at least two leaf neighbors, then for every integer $k\ge 1,{\text{sd}}_{{\gamma }_{[kR]}}(G)=1.$

Proof.

Let u, v be two leaves sharing the same neighbor w and let $G^{\prime }$ be the graph obtained from G by subdividing the edge uw with vertex subdivision x. If f is any [k]-RDF on $G^{\prime },$ then we must have $f(u)+f(x)\ge k$ and $f(w)+f(v)\ge k.$ In this case, let us define the function g on V(G) by $g(w)=k+1,g(u)=g(v)=0$ and $g(z)=f(z)$ for each $z\in V(G)\setminus \{u,v,w\}.$ Clearly, g is a [k]-RDF of G such that $\omega (g)<\omega (f)$ and hence ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1.$ □

Proposition 7.

Let G be a connected graph of order $n\ge 3$. Then for every integer $k\ge 1,$ if ${\gamma }_{[kR]}(G)=k+1$, then ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1.$

Proof.

Assume that ${\gamma }_{[kR]}(G)=k+1.$ By Observation 3, $\Delta (G)=n-1.$ Let v be a vertex with maximum degree $\Delta (G)$ and let $w\in N(v).$ Let $G^{\prime }$ be the graph resulting from G by subdividing the edge vw with vertex x. Then $\Delta (G^{\prime })<n(G^{\prime })-1=n$ and so ${\gamma }_{[kR]}(G^{\prime })\ge k+2$ by Observation 3, which leads to ${\text{sd}}_{{\gamma }_{[kR]}}(G)=1.$□

Proposition 8.

Let G be a connected graph of order $n\ge 3$ with $\delta (G)=1$. Then for every integer $k\ge 2,{\text{sd}}_{{\gamma }_{[kR]}}(G)\le 2.$

Proof.

Let $u\in V(G)$ be a leaf, v its support vertex and w a neighbor of v different from u. Clearly, if w is a leaf, then by Proposition 6, the result is valid. Hence we assume that w is not a leaf. Let $G^{\prime }$ be the graph resulting from G by subdividing the edges uv, vw with subdivision vertices x and y, respectively. Let f be a ${\gamma }_{[kR]}(G^{\prime })$-function such that f(u) is as small as possible. By Proposition 2 we may assume that $f(z)\ne 1$ for all vertex $z\in V(G^{\prime }).$ First suppose that f(x) = 0. By the choice of f we must have f(u) = k and we deduce from $f[N(x)]\ge k+|AN(x)|$ that $f(v)\ge 2.$ But then the function g defined by $g(w)=\min \{f(w)+f(y),k+1\},$ $g(v)=k+1,$ g(u) = 0 and $g(z)=f(z)$ otherwise, is a [k]-RDF of G of weight less that $\omega (f)$ yielding the desired result.

Assume now that $0<f(x)\le k.$ It follows from $f[N(u)]\ge k+|AN(u)|$ that $f(u)+f(x)\ge k+1.$ But then the function h defined by h(u) = 0, $h(x)=k+1$ and $h(z)=f(z)$ otherwise, is a [k]-RDF of $G^{\prime }$ of weight $\omega (f)$ which contradicts the choice of f.

Finally, let $f(x)=k+1.$ Then we have f(u) = 0. If $f(v)\ge 1,$ then the function g defined as before, is a [k]-RDF of G of weight less that $\omega (f)$ as desired. Hence assume that f(v) = 0. If f(y) = 0, then $f(w)=k+1$ and the function h defined on G by h(u) = k and $g(z)=f(z)$ otherwise, is a [k]-RDF of G of weight less that $\omega (f).$ If $f(y)\ge 1,$ then the function l defined on G by $l(v)=k+1$ and $l(z)=f(z)$ otherwise, is a [k]-RDF of G of weight less than $\omega (f).$ In either case, ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le 2.$□

Proposition 8 leads to the following corollary.

Corollary 9.

Let T be a tree of order at least 3. Then for every integer $k\ge 2,$ $${\text{sd}}_{{\gamma }_{\left[kR\right]}}(T)\le 2.$$

Furthermore, this bound is sharp for paths of order n with $n\equiv 2\hspace{1em}(\mathrm{mod}3).$

Theorem 10.

Let G be a connected graph and let v be a vertex of degree at least two. Then for every integer $k\ge 2,{\text{sd}}_{{\gamma }_{[kR]}}(G)\le \mathrm{deg}(v).$

Proof.

Let $t=\mathrm{deg}(v),N(v)=\{v_1,v_2,\dots ,v_t\}$ and let $G^{\prime }$ be the graph obtained from G by subdividing the edges $v{v}_1,v{v}_2,\dots ,v{v}_t$ with new vertices $x_1,x_2,\dots ,x_t,$ respectively. Let f be a ${\gamma }_{[kR]}(G^{\prime })$-function. If $f(v)+{\sum }_{i=1}^{t}f(x_i)\ge k+2,$ then the function g defined on V(G) by $g(v)=k+1$ and $g(z)=f(z)$ for $z\in V(G)\setminus \left\{v\right\},$ is a [k]-RDF of G with $\omega (g)<\omega (f)$ and hence ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \mathrm{deg}(v).$ Hence we can assume that $f(v)+{\sum }_{i=1}^{t}f(x_i)\le k+1.$ Recall that f is a [k]-RDF on $G^{\prime }$ and so $f(N[v])\ge k+|AN(v)|.$ If $f(v)=k+1,$ then let g be a function defined on V(G) by g(v) = k and $g(z)=f(z)$ otherwise. Clearly, g is a [k]-RDF of G with $\omega (g)<\omega (f)$ and hence ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \mathrm{deg}(v).$ Assume now that f(v) = k. Then by Proposition 2 and our earlier assumption we must have ${\sum }_{i=1}^{t}f(x_i)=0$ and thus $f(v_i)\ge 2$ for each $i\in \{1,\dots ,t\}.$ Since $t\ge 2,$ the function g defined on V(G) by $g(v)=k-1$ and $g(x)=f(x)$ for $x\in V(G)\setminus \left\{v\right\}$ is a [k]-RDF of G with $\omega (g)<\omega (f).$ Finally, assume that $2\le f(v)\le k-1.$ Then we deduce from ${\sum }_{i=1}^{t}f(x_i)+f(v)\le k+1$ and $f(N[v])\ge k+|AN(v)|$ that there exists some x_i, say without loss of generality, x₁, such that $f(v)+f(x_1)=k+1.$ In this case, define the function g on V(G) by g(v) = k and $g(z)=f(z)$ for each $z\in V(G)\setminus \left\{v\right\}.$ Clearly, g is a [k]-RDF of G with $\omega (g)<\omega (f)$ and hence ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \mathrm{deg}(v).$

Now assume that f(v) = 0. Then as above we must have $f(x_i)=k+1$ for some $i\in \{1,\dots ,t\},$ say i = 1 and $f(x_j)=0$ for all $j\in \{2,\dots ,t\}.$ Hence $f(v_i)=k+1$ for every $i\in \{2,\dots ,t\}.$ In that case, since $t\ge 2,$ the function g defined on V(G) by $g(v_1)=k$ and $g(z)=f(z)$ for $z\in V(G)\setminus \left\{v_1\right\}$ is a [k]-RDF of G with $\omega (g)<\omega (f).$ Therefore ${\gamma }_{[kR]}(G)\le \omega (g)<\omega (f)$ implying that ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \mathrm{deg}(v).$□

Based on Theorem 10, we deduce that ${\text{sd}}_{{\gamma }_{[kR]}}(G)$ is defined for every connected graph G of order $n\ge 3.$ In addition, we have the following consequences, one of which follows from the fact that every planar graph contains a vertex of degree at most 5.

Corollary 11.

For every connected graph G with $\delta \ge 2$ and $k\ge 2$ an integer, ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \delta .$

Corollary 12.

For every planar graph G and $k\ge 2$ an integer, ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le 5.$

In the sequel, we present an upper bound on the [k]-RDS-number in terms of δ₂ defined as follows. For a vertex $v\in V,$ let $N_2(v)$ denote the set of vertices of G that are at distance 2 from v, and let $d_2(v)=|N_2(v)|.$ In that case, ${\delta }_2(G)=\min \{d_2(v)|v\in V\text{and}{\mathrm{deg}}_G(v)\ge 2\}.$ We make use of the following lemmas in the proof of Theorem 17. Recall that the complete graph K₃ is called a triangle.

Lemma 13.

Let G be a connected graph of order $n\ge 3$ and let G have a vertex $v\in V(G)$ which is contained in a triangle uvw such that $N(u)\cup N(w)\subseteq N[v]$. Then for every integer $k\ge 2,{\text{sd}}_{{\gamma }_{[kR]}}(G)\le 3.$

Proof.

Let $G^{\prime }$ be the graph obtained from G by subdividing the edges vu, vw, uw with new vertices x, y, z respectively, and let g be a ${\gamma }_{[kR]}(G^{\prime })$-function. By Proposition 2 we may assume that $g(t)\ne 1$ for all vertices $t\in V(G^{\prime }).$ We claim that $g(u)+g(v)+g(w)+g(x)+g(y)+g(z)\ge k+2.$ First assume that $0\in \{f(x),f(y),f(z)\},$ say, without loss of generality, f(x) = 0. Then we must have $f(N[x])\ge k+|AN(x)|.$ If $0\notin \{f(u),f(v)\},$ then clearly $f(u)+f(v)\ge k+2$ as desired. Hence we can assume that $0\in \{f(u),f(v)\}.$ If f(u) = 0 (the case f(v) = 0 is similar), then $f(v)=k+1,$ and thus we must have for vertex z, $f(z)+f(w)\ge k$ which leads to the desired claim.

Now assume that $0\notin \{f(x),f(y),f(z)\}.$ If one of x, y, z is assigned k + 1, then the claim is valid. If $f(x)=f(y)=f(z)=k,$ then again, we are done. Hence assume, without loss of generality, that $1<f(x)<k.$ By definition, we have $f(x)+f(u)+f(v)\ge k+1$ and since $f(y)\ge 1$ the claim follows.

Define the function h on V(G) by $h(v)=k+1,h(u)=h(w)=0$ and $h(s)=f(s)$ for each $s\in V(G)\setminus \{v,u,w\}.$ Obviously h is a [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G),$ and thiscompletes the proof.□

Lemma 14.

Let G be a connected graph of order $n\ge 3$ and let G have a vertex $v\in V(G)$ which is contained in a triangle uvw such that $N(u)\subseteq N[v]$ and $N(w)\setminus N[v]\ne \varnothing$. Then for every integer $k\ge 2,$ $${\text{sd}}_{{\gamma }_{\left[kR\right]}}(G)\le 3+|N(w)\setminus N[v\left]\right|.$$

Proof.

Let $N(w)\setminus N[v]=\{w_1,w_2,\dots ,w_t\}$ and let $G^{\prime }$ be the graph obtained from G by subdividing the edges vu, vw, uw with new vertices x, y, z respectively, and by subdividing each edge ww_i with a new vertex z_i. Let g be a ${\gamma }_{[kR]}(G^{\prime })$-function. As seen in the proof of Lemma 13, we have $g(v)+g(u)+g(w)+g(x)+g(y)+g(z)\ge k+2.$ Define $h:V(G)\to \{0,1,2,\dots ,k+1\}$ by $h(v)=k+1,h(u)=h(w)=0,h(w_i)=\min \{g(w_i)+g(z_i),k+1\}$ for each $i\in \{1,\dots ,t\}$ and $h(s)=g(s)$ for any remaining vertex s. It is easy to see that h is a [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G^{\prime })$ and the proof is complete.□

Lemma 15.

Let G be a connected graph of order $n\ge 3$ and v a vertex of G of degree at least 2 such that

1. $N(y)\setminus N[v]\ne \varnothing$ for each $y\in N(v),$

2. there exists a pair of vertices α, β in N(v) such that $(N(\alpha )\cap N(\beta ))\setminus N[v]=\varnothing .$

Then for every integer $k\ge 2,{\text{sd}}_{{\gamma }_{[kR]}}(G)\le 3+|N_2(v)|.$

Proof.

Let $N(v)=\{v_1,v_2,\dots ,v_{\mathrm{deg}(v)}\}.$ Without loss of generality, assume that $\alpha =v_1$ and $\beta =v_2.$ Moreover, we will assume that the pair α, β is chosen first among the adjacent vertices in N(v). Hence if $\alpha \beta \in E(G),$ then we assume also that $v_1{v}_2\in E(G).$ In addition, let $S=\{v_1,v_2,\dots ,v_t\}$ be one of the largest subset of N(v) containing v₁, v₂ and such that every pair x, y of vertices of S satisfies (ii). According to item (i), let $N(v_i)\setminus N[v]=\{v_{i_1},v_{i_2},\dots ,v_{i_{l_i}}\}$ for each $i\in \{1,2,\dots ,t\}.$ Now consider the graph G₁ obtained from G by subdividing the edges vv₁ and vv₂ with new vertices x₁ and x₂, respectively, and for all $i\in \{1,2,\dots ,t\},$ each of the edges $v_i{v}_{i_j},1\le j\le l_i,$ with a new vertex $v^{i_j}.$ We put $T_i=\left\{v^{i_j}\right|1\le j\le l_i\}$ and $T={\cup }_{1\le i\le t}{T}_i.$ Furthermore, if v₁ and v₂ are adjacent, then we also subdivide the edge $v_1{v}_2$ with a vertex u. Let f be a ${\gamma }_{[kR]}(G_1)$-function such that $V_1=\varnothing .$ Assume first that $v_1{v}_2\in E(G).$ As in the proof of Lemma 13 we can see that $f(u)+f(v)+f(v_1)+f(v_2)+f(x_1)+f(x_2)\ge k+2.$ Then the function g defined on V(G) by $g(v)=k+1,g(v_1)=g(v_2)=0,g(v_{i_j})=\min \{f(v_{i_j})+f(v^{i_j}),k+1\}$ for all $i\in \{1,2,\dots ,t\}$ and all $j\in \{1,2,\dots ,l_i\}$ and $g(x)=f(x)$ otherwise, is $[k]-$ RDF of G of weight less than ${\gamma }_{[kR]}(G_1).$

Assume now that $v_1{v}_2\notin E(G).$ By the choice of v₁, v₂, we conclude that S is an independent set. Also to dominate x₁, x₂, we must have $f(v)+f(x_1)+f(x_2)+f(v_1)+f(v_2)\ge k+1.$ If $f(v)+f(x_1)+f(x_2)+{\sum }_{i=1}^{t}f(v_i)\ge k+2,$ then the function g defined on V(G) by $g(v)=k+1,g(v_i)=0$ for $i\in \{1,2,\dots ,t\},g(v_{i_j})=\min \{f(v_{i_j})+f(v^{i_j}),k+1\}$ for all $i\in \{1,2,\dots ,t\}$ and all $j\in \{1,2,\dots ,l_i\}$ and $g(x)=f(x)$ otherwise, is a [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G_1).$ Thus we may assume that $f(v)+f(x_1)+f(x_2)+{\sum }_{i=1}^{t}f(v_i)=k+1.$ It follows that $f(v)=k+1,$ otherwise we must have $f(x_1)+f(x_2)+f(v_1)+f(v_2)\ge k+2,$ which is a contradiction. Hence $f(x_1)+f(x_2)+{\sum }_{i=1}^{t}f(v_i)=0.$ To [k]-Roman dominate $v^{i_j}$ we must have $f(v_{i_j})+f(v^{i_j})\ge k$ for all $i\in \{1,2,\dots ,t\}$ and all $j\in \{1,2,\dots ,l_i\}.$ Define the function g on V(G) by g(v) = k, $g(v_{i_j})=\min \{f(v_{i_j})+f(v^{i_j}),k+1\}$ for all $i\in \{1,3,\dots ,t\}$ and all $j\in \{1,2,\dots ,l_i\},$ and $g(x)=f(x)$ otherwise. Since each vertex of $N(v)-S$ has a common neighbor with v_i in $N_2(v)$ for some $i\in \{1,\dots ,t\},$ the function g is a [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G_1).$ In each of the previous situations we saw that the graph G has a [k]-RDF of weight less than ${\gamma }_{[kR]}(G_1).$ Moreover, since G₁ was obtained by inserting at most $3+\left|T\right|\le 3+|N_2(v)|$ new vertices, we deduce that ${\text{sd}}_{{\gamma }_{[R]}}(G)\le 3+|N_2(v)|.$ This complete the proof.□

Lemma 16.

Let G be a connected graph of order $n\ge 3$ and let v be a vertex of G of degree at least 2 such that

1. $N(y)\setminus N[v]\ne \varnothing$ for each $y\in N(v)$

2. for every pair of vertices α, β in $N(v),(N(\alpha )\cap N(\beta ))\setminus N[v]\ne \varnothing .$

Then for every integer $k\ge 2,$ ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le 3+|N_2(v)|.$

Proof.

If $\mathrm{deg}(v)\le 3+|N_2(v)|,$ then the result is immediate from Theorem 10. Hence assume that $\mathrm{deg}(v)\ge 4+|N_2(v)|,$ and let $N(v)=\{v_1,v_2,\dots ,v_t\}$ and set $X_1=N(v_1)-N[v]=\{w_1,w_2,\dots ,w_p\}.$ By item (ii), each $y\in N(v)\setminus \left\{v_1\right\}$ has a neighbor in X₁. Let T be one of the largest subset of $N(v)\setminus \left\{v_1\right\}$ such that for each $T_1\subseteq T$ we have $|N(T_1)\setminus (N[v]\cup X_1)|\ge \left|T_1\right|.$ Note that such a set T may not exist, but the inequality $|N_2(v)|\ge \left|X_1\right|+\left|T\right|$ is still verified. Moreover, every vertex u in $U=N(v)\setminus (T\cup \{v_1\})$ has a neighbor in X₁ and $N(u)\setminus N[v]\subseteq X_1\cup N(T).$ In addition X₁ dominate N(v) (by item (ii)). It follows from $$4+\left|X_1\right|+\left|T\right|\le 4+|N_2(v)|\le \mathrm{deg}(v)=\left|T\right|+1+\left|U\right|$$ that $\left|U\right|\ge 4.$ If $T\ne \varnothing ,$ then, without loss of generality, let $T=\{v_2,v_3,\dots ,v_s\}.$

Let G₁ be the graph obtained from G by subdividing the edges $v_1{w}_j$ with new vertices y_j for all $j\in \{1,2,\dots ,p\}$ and the edges vv_i with new vertices x_i for $i\in \{1,\dots ,s+2\}$ when $T\ne \varnothing$ or $i\in \{1,2,3\}$ when $T=\varnothing .$ Therefore $\left|X_1\right|+\left|T\right|+3$ edges of G are subdivided. Recall that $\left|X_1\right|+\left|T\right|+3\le |N_2(v)|+3.$ Let f be a ${\gamma }_{[kR]}(G_1)$-function such that $V_1=\varnothing .$ If $f(v)+f(v_1)+{\sum }_{i=1}^{s+2}f(x_i)\ge k+2,$ then the function g defined on V(G) by $g(v)=k+1,g(w_j)=\min \{k+1,f(w_j)+f(y_j)|1\le j\le p\}$ and $g(x)=f(x)$ otherwise, is [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G),$ yielding the result. Hence we assume that (2) $$f(v)+f(v_1)+\sum _{i=1}^{s+2}f(x_i)\le k+1.$$(2)

If f(v) = k, then to [k]-Roman dominate x₁ we must have $f(x_1)+f(v_1)\ge 2$ which contradicts (2). Hence $f(v)\ne k.$ Consider the following cases depending on the values of f(v).

Case 1.

$f(v)=k+1.$

It follows from (2) that $f(v_1)={\sum }_{i=1}^{s+2}f(x_i)=0.$ If ${\sum }_{i=1}^{p}f(y_i)\ge k+2,$ then the function g defined on V(G) by $g(v_1)=k+1,$ and $g(x)=f(x)$ otherwise, is a [k]-RDF of weight less than ${\gamma }_{[kR]}(G_1).$ Thus we may assume that ${\sum }_{i=1}^{p}f(y_i)\le k+1.$ Observe that if $f(y_j)=0$ for some j, then since $f(v_1)=0,$ we deduce that $f(w_j)=k+1.$ Moreover, if $2\le f(y_j)\le k-1,$ then $f(w_j)+f(y_j)\ge k+1.$ Using the fact that each v_i has a neighbor in X₁, it follows that the function g defined on V(G) by $g(v)=k,g(w_j)=\min \{k+1,g(y_j)+g(w_j)\}$ for each $j\in \{1,2,\dots ,p\}$ and $g(x)=f(x)$ otherwise is an [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G_1).$ In either case, the desired result follows.

Case 2.

f(v) = 0.

To [k]-Roman dominate x₁, we must have $f(x_1)+f(v_1)\ge k.$ On the other hand, $f(x_1)+f(v_1)\le k+1$ by (2). We deduce from $V_1=\varnothing$ that $f(x_i)=0$ for each $2\le i\le s+2$ and so $f(v_i)=k+1$ for each $i\in \{2,\dots ,s+2\}.$ In this case, define the function g on V(G) by $g(v_1)=g(v)=k+1,g(v_{s+1})=g(v_{s+2})=0$ and $g(x)=f(x)$ otherwise. Since $N(v_i)\setminus N[v]\subseteq X_1\cup N(T)$ for $i\in \{s+1,s+2\},$ one can easily seen that g is a [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G_1)$ leading to the desired result.

Case 3.

$f(v)\in \{2,\dots ,k-1\}.$

Let $f(v)=\mathcal{l}.$ If $f(v_1)\ge 1,$ then we must have $f(v_1)+f(x_1)\ge k-\mathcal{l}+2$ which contradicts (2). Hence assume that $f(v_1)=0.$ Then we must have $f(x_1)\ge k-\mathcal{l}+1,$ and thus the function g defined on G by g(v) = k, $g(w_i)=\min \{f(w_i)+f(y_i),k+1\}$ for $1\le i\le p,$ and $g(x)=f(x)$ otherwise, is a [k]-RDF of G of weight less than ${\gamma }_{[kR]}(G_1).$ In either case, ${\gamma }_{[kR]}(G)<{\gamma }_{[kR]}(G_1),$ and this completes the proof.□

We are now ready to state and prove the main result of this section.

Theorem 17.

Let G be a connected graph of order $n\ge 3$. Then for every integer $k\ge 2,$ $$s{d}_{{\gamma }_{\left[kR\right]}(G)}\le 3+\min \{d_2(v):v\in V\text{and}\mathrm{deg}(v)\ge 2\}.$$

Proof.

If G is a star $K_{1,n-1},$ then $s{d}_{{\gamma }_{[kR]}(G)}=1,$ and thus the result is valid. Hence assume that G is not a star. If G has a leaf, then by Proposition 8, the result is valid again. Hence we assume that G is a graph with $\delta (G)\ge 2.$ According to Lemmas 13, 14, 15 and 16 we have $s{d}_{{\gamma }_{[kR]}(G)}\le 3+\min \{d_2(v);v\in V\text{and}\mathrm{deg}(v)\ge 2\}.$□

The following two corollaries are immediate consequences of Theorem 17. Notice that for a vertex v of degree Δ, $|N_2(v)|\le n-\Delta -1.$

Corollary 18.

Let G be a connected graph of order $n\ge 3$. Then for every integer $k\ge 2,$ $\text{sd}$${}_{{\gamma }_{[4R]}(G)}\le {\delta }_2(G)+3.$

Corollary 19.

Let G be a connected graph of order $n\ge 3$. Then for every integer $k\ge 2,{\text{sd}}_{{\gamma }_{[kR]}}(G)\le n-\Delta +2.$

Theorem 20.

Let G be a connected graph of order $n\ge 3$. Then for every integer $k\ge 2,{\text{sd}}_{{\gamma }_{[kR]}}(G)\le \frac{n}{2}+1.$

Proof.

If G is a star $K_{1,n-1},$ then $s{d}_{{\gamma }_{[kR]}(G)}=1,$ and thus the result is valid. Hence assume that G is not a star. If G has a leaf, then by Proposition 8, the result is valid again. Hence we assume that G is a graph with $\delta (G)\ge 2.$ If $\delta (G)\le \frac{n}{2}+1,$ then the result follows from Corollary 11. Assume that $\delta (G)\ge \frac{n}{2}+2.$ Corollary 19 leads to ${\text{sd}}_{{\gamma }_{[kR]}}(G)\le \frac{n}{2}$ as desired.□