Wensheng Li^*, Zhongsheng Huang, Zhifang Feng
School of Sciences, Langfang Normal University, Langfang, China.
DOI: 10.4236/ojdm.2026.162002   PDF    HTML   XML   26 Downloads   191 Views   Citations

Abstract

A double Roman dominating function (DRDF) $f$ on a given graph $G$ is a mapping from$V\left(G\right)$ to {0, 1, 2, 3} in such a way that a vertex $v$ for which $f\left(v\right)=0$ has at least a neighbor labeled 3 or two neighbors both labeled 2 and a vertex $v$ for which $f\left(v\right)=1$ has at least a neighbor labeled 2 or 3. The weight of a DRDF $f$ is the value $w\left(f\right)={\displaystyle {\sum }_{v\in V\left(G\right)}f\left(v\right)}$ . The minimum weight of a DRDF on a graph $G$ is called the double Roman domination number of $G$ . In this paper, we determine the exact value of the double Roman domination number of the Spider graphs $S_{m,2}$ and $S_{m,3}$ , and obtain an upper bound of the Spider graphs $S_{m,n}$ .

Keywords

Double Roman Dominating Function, Double Roman Domination Number, Spider Graphs

Share and Cite:

1. Introduction

Let $G=\left(V,E\right)$ be a graph without loops and multiple edges, where $V\left(G\right)$ and $E\left(G\right)$ are the vertex set and edge set of $G$ , respectively. If$uv\in E\left(G\right)$ , we say that vertices $u$ and $v$ are adjacent, and $u$ is a neighbor of $v$ . The open neighborhood of $v$ , denoted by $N\left(v\right)$ , is a set $\left\{u|uv\in E\right\}$ . And the close neighborhood of $v$ , denoted by $N\left[v\right]$ , is a set $N\left(v\right)\cup \left\{v\right\}$ . A function $f:V\to \left\{0,1,2,3\right\}$ is a double Roman dominating function if a vertex$v$ for which $f\left(v\right)=0$ has at least a neighbor labeled 3 or two neighbors both labeled 2 and a vertex $v$ for which $f\left(v\right)=1$ has at least a neighbor labeled 2 or 3. The sum of the function values of all vertices in $N\left[v\right]$ , denoted by $f\left[v\right]$ , is $f\left[v\right]={\displaystyle {\sum }_{u\in N\left[v\right]}f\left(u\right)}$ . The weight of $f$ , denoted by $\omega \left(f\right)$ , is the sum of the function values of all vertices in $G$ . The double Roman domination number, denoted by ${\gamma }_{dR}\left(G\right)$ , equals the minimum weight of a double Roman dominating function on $G$ , and a double Roman dominating function of $G$ with weight ${\gamma }_{dR}\left(G\right)$ is called a ${\gamma }_{dR}$ -function of $G$ .

The double Roman domination was introduced in [1] and has been studied in [2]-[9]. Double Roman domination for cardinal products of graphs was studied in [2], and double Roman trees were characterized in [3]. It is known that the decision problem associated with ${\gamma }_{dR}\left(G\right)$ is NP-complete for bipartite and chordal graphs, undirected path graphs, chordal bipartite graphs, and circle graphs [4]-[6]. Closely related problems to double Roman domination were studied in [7]-[9].

A Spider is a tree with at most one vertex of degree more than two, called the center of Spider (if no vertex of degree more than two, then any vertex can be the center). A leg of a Spider is a path from the center to a vertex of degree one. If each leg of a Spider has the same length $n$ , we denote the Spider as $S_{m,n}$ with $m$ legs $P_1,P_2,\cdots ,P_m$ . $P_i=c{v}_{i,1}{v}_{i,2}\cdots v_{i,n}$ , where $c$ is the center of $S_{m,n}$ . $S_{m,2}$ is shown in Figure 1, which has $2m+1$ vertices.

Figure 1. The spider graph $S_{m,2}$ .

In [4], the authors studied the double Roman domination number of trees and presented a tight lower bound based on the domination number. As a special class of trees, Spider graphs possess a more unique structure, which motivates us to investigate whether stronger results can be derived. In particular, it is natural to explore whether the exact value of the double Roman domination number can be determined for Spider graphs. In this paper, we carry out a study along this line and obtain corresponding results. We determine the exact double Roman domination numbers of Spider graphs $S_{m,2}$ and $S_{m,3}$ , and present an upper bound on the double Roman domination number of $S_{m,n}$ in terms of the order.

The following proposition will be used.

Proposition A [7] In a double Roman dominating function of weight ${\gamma }_{dR}\left(G\right)$ , no vertex needs to be assigned the value 1.

2. Double Roman domination in Spider Graphs

Lemma 1. Let $f$ be a DRDF on $G$ and $v$ is a leaf of $G$ . Then $f\left[v\right]\ge 2$ .

Proof: Let $f$ be a DRDF on$G$ . Since $v$ is a leaf of $G$ , there is only one element in $N\left(v\right)$ , denoted by $u$ . If $f\left(v\right)=2$ or 3, the conclusion is obvious. If $f\left(v\right)=0$ or 1, by the definition of DRDF, we have $f\left(u\right)\ge 2$ . Thus $f\left[v\right]\ge 2$ . In conclusion, the assertion follows. ☐

Lemma 2. Let $f$ be a DRDF on $S_{m,2}$ and $f\left(c\right)=0$ . Then $f\left[v_{i,2}\right]\ge 3$ , where $1\le i\le m$ .

Proof: Let $f$ be a DRDF on $S_{m,2}$ and $f\left(c\right)=0$ . $v_{i,2}$ is a leaf of $S_{m,2}$ , where $1\le i\le m$ .

Case 1 $f\left(v_{i,2}\right)=0$ . By the definition of DRDF, we have $f\left(v_{i,1}\right)=3$ . Thus $f\left[v_{i,2}\right]=3$ .

Case 2 $f\left(v_{i,2}\right)=1$ . By the definition of DRDF, we have 3 $f\left(v_{i,1}\right)=2$ or. Thus $f\left[v_{i,2}\right]\ge 3$ .

Case 3 $f\left(v_{i,2}\right)=2$ . Since$f\left(c\right)=0$ , by the definition of DRDF, we have $f\left(v_{i,1}\right)\ne 0$ , which means$f\left(v_{i,1}\right)\ge 1$ . Thus, $f\left[v_{i,2}\right]\ge 3$ .

Case 4 $f\left(v_{i,2}\right)=3$ . Obviously, we have $f\left[v_{i,2}\right]\ge 3$ .

In conclusion, the assertion follows. ☐

Theorem 1. For a Spider $S_{m,2}$ with $m\ge 2$ , ${\gamma }_{dR}\left(S_{m,2}\right)=2m+2$ .

Proof: Consider the mapping $f:V\left(S_{m,2}\right)\to \left\{0,1,2,3\right\}$ , such that $f\left(c\right)=2$ , $f\left(v_{i,1}\right)=0$ and $f\left(v_{i,2}\right)=2$ , where $1\le i\le m$ ,as illustrated in Figure 2. Then $f$ is a DRDF on $S_{m,2}$ and $\omega \left(f\right)=2m+2$ . Thus, ${\gamma }_{dR}\left(S_{m,2}\right)\le 2m+2$ .

Figure 2. The mapping $f:V\left(S_{m,2}\right)\to \left\{0,2,3\right\}$ .

On the other hand, by Proposition A, let $g$ be a ${\gamma }_{dR}$ -function of $S_{m,2}$ with no vertex assigned value 1. By Lemma 1, we have

$\begin{array}{c}\omega \left(g\right)=g\left(c\right)+{\displaystyle {\sum }_{i=1}^{m}g\left[v_{i,2}\right]}\\ =g\left(c\right)+g\left[v_{1,2}\right]+g\left[v_{2,2}\right]+{\displaystyle {\sum }_{i=3}^{m}g\left[v_{i,2}\right]}\\ \ge g\left(c\right)+g\left[v_{1,2}\right]+g\left[v_{2,2}\right]+2\left(m-2\right)\end{array}$ .

In the following, we will show that $g\left(c\right)+g\left[v_{1,2}\right]+g\left[v_{2,2}\right]\ge 6$ . If $g\left(c\right)=0$ , by Lemma 2, $g\left[v_{1,2}\right]\ge 3$ and $g\left[v_{2,2}\right]\ge 3$ . Thus $g\left(c\right)+g\left[v_{1,2}\right]+g\left[v_{2,2}\right]\ge 6$ . If $g\left(c\right)=2$ or 3, by Lemma 1, we have $g\left[v_{1,2}\right]\ge 2$ and $g\left[v_{2,2}\right]\ge 2$ . Thus, $g\left(c\right)+g\left[v_{1,2}\right]+g\left[v_{2,2}\right]\ge 6$ .

In conclusion, we have ${\gamma }_{dR}\left(S_{m,2}\right)=w\left(g\right)\ge 2m+2$ . Therefore, ${\gamma }_{dR}\left(S_{m,2}\right)=2m+2$ .☐

Lemma 3. Let $f$ be a DRDF on $S_{m,3}$ , then $f\left[v_{i,2}\right]\ge 3$ , where $1\le i\le m$ .

Proof: Let $f$ be a DRDF on $S_{m,3}$ . The open neighborhood of $v_{i,2}$ , denoted by $N\left(v_{i,2}\right)$ , is the set $\left\{v_{i,1},v_{i,3}\right\}$ , where $1\le i\le m$ .

Case 1 $f\left(v_{i,2}\right)=0$ . By the definition of DRDF, at least one element of $N\left(v_{i,2}\right)$ is assigned 3 or both vertices are assigned 2. Thus $f\left[v_{i,2}\right]=f\left(v_{i,1}\right)+f\left(v_{i,2}\right)+f\left(v_{i,3}\right)\ge 3$ .

Case 2 $f\left(v_{i,2}\right)=1$ . By the definition of DRDF, at least one element of $N\left(v_{i,2}\right)$ is assigned 2 or 3. Thus $f\left[v_{i,2}\right]=f\left(v_{i,1}\right)+f\left(v_{i,2}\right)+f\left(v_{i,3}\right)\ge 3$ .

Case 3 $f\left(v_{i,2}\right)=2$ . By the definition of DRDF, we have $f\left(v_{i,3}\right)\ne 0$ , which means$f\left(v_{i,3}\right)\ge 1$ . Thus, $f\left[v_{i,2}\right]\ge 3$ .

Case 4 $f\left(v_{i,2}\right)=3$ . Obviously, we have $f\left[v_{i,2}\right]\ge 3$ .

In conclusion, the assertion follows.

Theorem 2. For a Spider $S_{m,3}$ with $m\ge 2$ , ${\gamma }_{dR}\left(S_{m,3}\right)=3m+2$ .

Proof: Consider the mapping $f:V\left(S_{m,3}\right)\to \left\{0,1,2,3\right\}$ , such that $f\left(c\right)=2$ ,$f\left(v_{i,1}\right)=f\left(v_{i,3}\right)=0$ and $f\left(v_{i,2}\right)=3$ , where $1\le i\le m$ , as illustrated in Figure 3. Then $f$ is a DRDF on $S_{m,3}$ and $\omega \left(f\right)=3m+2$ . Thus, ${\gamma }_{dR}\left(S_{m,3}\right)\le 3m+2$ .

Figure 3. The mapping $f:V\left(S_{m,3}\right)\to \left\{0,2,3\right\}$ .

On the other hand, let $g$ be a ${\gamma }_{dR}$ -function of $S_{m,3}$ with no vertex assigned value 1. Next, we proceed by case analysis on the assignment of vertex $c$ .

Case 1 $g\left(c\right)=0$ .

By the definition of DRDF, at least one element of $N\left(c\right)$ is assigned 3 or two vertices of $N\left(c\right)$ are assigned 2. If at least one element of $N\left(c\right)$ is assigned 3, without loss of generality, we assume that the value of $v_{1,1}$ is assigned 3. By Lemma 1 and Lemma 3, we have

$\begin{array}{c}\omega \left(g\right)=g\left(c\right)+g\left(v_{1,1}\right)+g\left[v_{1,3}\right]+{\displaystyle {\sum }_{i=2}^{m}g\left[v_{i,2}\right]}\\ \ge 0+3+2+3\left(m-1\right)\\ =3m+2.\end{array}$

If there are two vertices of $N\left(c\right)$ assigned 2, without loss of generality, we assume that the values of $v_{1,1}$ and $v_{2,1}$ are assigned 2. By Lemma 1, we have

$\begin{array}{c}\omega \left(g\right)=g\left(c\right)+g\left(v_{1,1}\right)+g\left[v_{1,3}\right]+g\left(v_2\right)+g\left[v_{2,3}\right]+{\displaystyle {\sum }_{i=3}^{n}g\left[v_{i,2}\right]}\\ \ge 0+2+2+2+2+3\left(m-2\right)\\ =3m+2.\end{array}$

Case 2 $g\left(c\right)=2$ or 3.

By Lemma 3, we have

$\begin{array}{c}\omega \left(g\right)=g\left(c\right)+{\displaystyle {\sum }_{i=1}^{m}g\left[v_{i,2}\right]}\\ \ge 3m+2.\end{array}$

From above, we have ${\gamma }_{dR}\left(S_{m,3}\right)=\omega \left(g\right)\ge 3m+2$ . Thus, ${\gamma }_{dR}\left(S_{m,3}\right)=3m+2$ .

Theorem 3. For a Spider graph $S_{m,n}$ with $m\ge 2$ and $n\ge 4$ , ${\gamma }_{dR}\left(S_{m,n}\right)\le m\cdot n+2$ .

Proof: Let $S_{m,n}$ be a Spider graph with $m$ legs and each leg is a path of length $n$ . If $n\equiv 0\left(\mathrm{mod}2\right)$ , we consider the mapping $f:V\left(S_{m,n}\right)\to \left\{0,2,3\right\}$ , such that $f\left(c\right)=2$ and

$f\left(v_{i,j}\right)=\{\begin{array}{ll}0\hfill & j\equiv 1\left(\mathrm{mod}2\right)\hfill \\ 2\hfill & j\equiv 0\left(\mathrm{mod}2\right)\hfill \end{array}$ ,

where $1\le i\le m$ . Then $f$ is a DRDF on $S_{m,n}$ and $\omega \left(f\right)=m\cdot n+2$ . Thus, ${\gamma }_{dR}\left(S_{m,n}\right)\le m\cdot n+2$ . The mapping is illustrated in Figure 4(a) with $m=3$ and $n=4$ . If $n\equiv 1\left(\mathrm{mod}2\right)$ , we consider the mapping$f:V\left(S_{m,n}\right)\to \left\{0,2,3\right\}$ , such that $f\left(c\right)=2$ and

$f\left(v_{i,j}\right)=\{\begin{array}{ll}0\hfill & j\equiv 1\left(\mathrm{mod}2\right)\hfill \\ 2\hfill & j\equiv 0\left(\mathrm{mod}2\right)\text{and}j<n-1\hfill \\ 3\hfill & j=n-1w\hfill \end{array}$ ,

where $1\le i\le m$ . Then $f$ is a DRDF on $S_{m,n}$ and $\omega \left(f\right)=m\cdot n+2$ . Thus, ${\gamma }_{dR}\left(S_{m,n}\right)\le m\cdot n+2$ . The mapping is illustrated in Figure 4(b) with $m=3$ and $n=5$ .

In conclusion, the assertion follows.

Figure 4. The values assigned on $S_{m,n}$ . (a) m = 3, n = 4; (b) m = 3, n = 5.

3. Conclusion

As an important and well-studied class of graphs, spider graphs have attracted considerable attention in the literature. In this paper, we determine the exact values of the double Roman domination numbers for two particular spider graphs$S_{m,2}$ and $S_{m,3}$ . Furthermore, we establish an upper bound for the double Roman domination number of the general spider graph $S_{m,n}$ . Given the relatively clear structure of spider graphs, their double Roman domination numbers are expected to be well-determined, which will be further explored in our future work.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Beeler, R.A., Haynes, T.W. and Hedetniemi, S.T. (2016) Double Roman Domination. Discrete Applied Mathematics, 211, 23-29.[CrossRef]
[2]	Klobučar, A. and Klobučar, A. (2020) Properties of Double Roman Domination on Cardinal Products of Graphs. Ars Mathematica Contemporanea, 19, 337-349.[CrossRef]
[3]	Ahangar, H.A., Amjadi, J., Atapour, M., Chellali, M. and Sheikholeslami, S.M. (2019) Double Roman Trees. Ars Combinatoria, 145, 173-183. https://combinatorialpress.com/ars/vol145/
[4]	Abdollahzadeh Ahangar, H., Chellali, M. and Sheikholeslami, S.M. (2017) On the Double Roman Domination in Graphs. Discrete Applied Mathematics, 232, 1-7.[CrossRef]
[5]	Banerjee, S., Henning, M.A. and Pradhan, D. (2020) Algorithmic Results on Double Roman Domination in Graphs. Journal of Combinatorial Optimization, 39, 90-114.[CrossRef]
[6]	Jafari Rad, N. and Rahbani, H. (2019) Some Progress on the Double Roman Domination in Graphs. Discussiones Mathematicae Graph Theory, 39, 41-53.[CrossRef]
[7]	Meena, J., Malini Mai, T.N.M., Suresh, M.L., Rathour, L. and Mishra, L.N. (2026) Double Roman Domination in Some Graphs. Discrete Mathematics, Algorithms and Applications, 18, Article ID: 2550016.[CrossRef]
[8]	Hamja, J., Sheikholeslami, S.M., Esmaeeli, M., Cris L. Armada, and Aniversario, I.S. (2025) Independent Double Roman Domination Stability in Graph. European Journal of Pure and Applied Mathematics, 18, Article 5984.[CrossRef]
[9]	Zec, T., Matić, D. and Djukanović, M. (2025) On Double Roman Domination Problem for Several Graph Classes. Aequationes mathematicae, 99, 439-463.[CrossRef]