# New Bounds on the Triple Roman Domination Number of Graphs

Authors: M. Hajjari; H. Abdollahzadeh Ahangar; R. Khoeilar; Z. Shao; S. M. Sheikholeslami
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In this paper, we derive sharp upper and lower bounds on the sumγ3RG+γ3RG¯ and product γ3RGγ3RG¯, where G¯ is the complement of graph G. We also show that for each tree T of order n≥2, γ3RT≤3n+sT/2 and γ3RT≥⌈4nT+2−ℓT/3⌉, where sT and ℓT are the number of support vertices and leaves of T.


---

## Body

## 1. Terminology and Introduction

For notation and graph theory terminology, we, in general, follow Haynes et al. [1]. Throughout this paper, G denotes a simple graph, with vertex set V=VG and edge set E=EG. The order VG of G is denoted by n=nG. The open neighborhood of v is the set Nv=u∈VG|uv∈EG, and the closed neighborhood of v is the set Nv=Nv∪v. The degree of a vertex v∈V is degGv=degv=Nv. The minimum and maximum degree of a graph G are denoted by δG=δ and ΔG=Δ, respectively. The complement of a graph is denoted by G¯. The distance du,v between two vertices u and v of a (connected) graph G is the length of a shortest u,v-path in G. The maximum distance among all pairs of vertices in G is the diameter of G, which is denoted by diam G. For a subset X of vertices of G, we denote by GX the subgraph induced by X. A vertex of degree one is called a leaf and its neighbor a support vertex. For a vertex v in a rooted tree T, the maximal subtree at v is the subtree of T induced by v and its descendants and is denoted by Tv.In the field of chemistry, graph theory has provided many useful tools, such as topological indices. Cheminformatics is one of the latest concepts which is a join of chemistry, mathematics, and information science.Topological indices and domination in graphs are the essential topics in the theory of graphs. Topological indices are numerical parameters of the graph, such that these parameters are the same for the graph in which they are isomorphism. In [2], the study introduced the concept of domination degree of the vertex v. Some of the major classes of topological indices are distance-based topological indices and degree-based topological indices. Degree-based topological indices are of great significance. Relationships between various topological indices and domination number of graphs have been the focus of interest of the researchers for quite many years, and this direction is continuously vital (see [3–5]). Specifically, Ahmad Jamri et al. [6, 7] investigated extremal Zagreb indices of graphs with a given Roman domination number.Letk≥1 be an integer and G be a finite and simple graph with vertex set VG. Let f be a function that assigns label from the set S:=0,1,2,…,k+1 to the vertices of a graph G. For a vertex v∈VG, the active neighborhood of v, denoted by ANv, is the set of vertices w∈NGv such that fw≥1. A k-RDF is a function f:VG⟶S satisfying the condition that for any vertex v∈VG with fv<k,fNGv≥ANv+k. The weight of a k-RDF is ωf=Σv∈VGfv. The k-Roman domination number γkRG of G is the minimum weight of an k-RDF on G. The case k=1 is the usual Roman domination which has been introduced in [8]. For more details on Roman domination and its variants, we refer the reader to [9]. The case k=2 is called double Roman domination and has been studied in [10–12], while the case k=3 is called the triple Roman domination and has been studied in [13, 14].The Roman domination in graphs is well studied in graph theory. The topic is related to a defensive strategy problem in which the Roman legions are settled in some secure cities of the Roman Empire. The deployment of the legions around the Empire is designed in such a way that a sudden attack to any undefended city could be quelled by a legion from a strong neighbor. There is an additional condition: no legion can move and doing so leaves its base city defenceless. In this paper, we continue the study of a variant of Roman domination in graphs: the triple Roman domination. We consider that any city of the Roman Empire must be able to be defended by at least three legions. These legions should be either in the attacked city or in one of its neighbors. We determine various bounds on the triple Roman domination number for general graphs, and we give exact values for some graph families. Moreover, complexity results are also obtained.For the graph parameterρ, bounds for the sum ρG+ρG¯ or product ρG×ρG¯ are called results of “Nordhaus–Gaddum” type, honoring the paper of Nordhaus–Gaddum [15] obtaining such bounds when ρ is the chromatic number.In this paper, we first present Nordhaus–Gaddum-type bounds for the triple Roman domination number. For each treeT of order n≥2, we also show that γ3RT≤3n+sT/2 and γ3RT≥⌈4nT+2−ℓT/3⌉.We will use the next results in this paper. Letℱ be the family of all trees that can be built from k ≥ 1 paths P4=v1iv2iv3iv4i1≤i≤k by adding k − 1 edges incident with the v2i’s, so that they induce a connected subgraph. (see Figure 1).Figure 1
Familyℱ.Theorem 1.
For any connected graphG of order n≥2, γ3RG≤7n/4 with equality if and only if G∈ℱ.Theorem 2.
For each connected graphG, there exists a γ3RG-function that does not value the label one to each vertex in G.Theorem 3.
LetG be a connected graph on n≥1 vertices. Then, γ3RG=3 if and only if G=K1.Theorem 4.
IfG is a connected graph on n≥2 vertices, then γ3RG=4 if and only if Δ=n−1.Theorem 5.
There is no connected graph of ordern for which γ3RG=5.Theorem 6.
IfG is a connected graph on n vertices, then γ3RG=6 if and only if there are two nonjoin vertices in VG with degree ΔG=n−2.


## 2. Nordhaus–Gaddum Inequality for the 3RD Numbers

In this section, we present Nordhaus–Gaddum-type inequalities for the triple Roman domination numbers of graphs. We begin with a simple result.Lemma 1.
IfG is a graph of order n and maximum degree ΔG, then(1)γ3RG≤3n−3ΔG+1.Moreover, ifΔG<n−1 and γ3RG=3n−3ΔG+1, then γ3RG¯≤1+3ΔG.Proof.
Supposeb is a vertex of maximum degree Δ. Clearly Nb,∅,∅,VG−Nb,b is a 3RD-function of weight 3n−3Δ+1 and so γ3RG≤3n−3Δ+1.
LetΔG<n−1 and γ3RG=3n−3Δ+1. Let b∈VG be a vertex with maximum degree ΔG, and let B=VG−Nb. Suppose that z∈B is a vertex with maximum degree in GB. If u has a neighbor in B, then the function l=Nz∪Nb,∅,∅,VG−Nb∪Nz,z,b is a 3RD-function of G of weight smaller than γ3RG, a contradiction. Therefore, ΔGB=0. If Nb=Nz, then Nb,∅,∅,VG−Nb,∅ is a 3RD-function of G of weight 3n−3ΔG which is a contradiction. Hence, there is a vertex t∈Nb for which zt∉EG. Then, B−z∪b,t,∅,∅,Nb−t,z is a 3RDF of G¯ of weight 3Δ−1+4 as desired. □Theorem 7.
IfG is a graph of order n and n≥2, then(2)10≤γ3RG+γ3RG¯≤3n+4.Equality holds for the lower bound if and only ifG or G¯ is K2, and equality holds for the upper bound if and only if G or G¯ is a complete graph.Proof.
We can suppose thatγ3RG≤γ3RG¯. First, we show the left inequality. If γ3RG≥6, then γ3RG+γ3RG¯≥12 as desired. Let γ3RG≤5. By Theorems 3 and 5, we find γ3RG=4, and Theorem 4 follows that ΔG=n−1. Hence, G¯ is disconnected and so γ3RG¯≥6. Thus, γ3RG+γ3RG¯≥10. If the equality holds, then we should have γ3RG¯=6. As noted, G has a vertex of degree n−1, say b. Since b is an isolated vertex in G¯, we find that n=2 and, consequently, G=K2.
Next, we show the upper bound. By Lemma1, we find γ3RG≤3n−3ΔG+1 and γ3RG¯≤3n−3ΔG¯+1. If γ3RG≤3n−3ΔG and γ3RG¯≤3n−3ΔG¯, then we find(3)γ3RG+γ3RG¯≤3n−3ΔG+3n−3ΔG¯=3n−3ΔG+3δG+3≤3n+1.
Suppose thatγ3RG=3n−3ΔG+1. If ΔG<n−1, then Lemma 1 follows that γ3RG¯≤1+3ΔG and so(4)γ3RG+γ3RG¯≤3n−3ΔG+1+3ΔG+1≤3n+2.
SupposeΔG=n−1. Then, we have γ3RG is equal to four. If ΔG¯≥1, then we have(5)γ3RG+γ3RG¯≤4+3n−3ΔG¯+1≤3n+2.
Suppose thatΔG¯=0. Then, G is complete graph, and clearly, we have γ3RG+γ3RG¯=3n+4. This completes the proof. □
To prove an upper bound on the productγ3RGγ3RG¯, we use the following result in [13].Theorem 8.
LetG be a graph of order n and minimum degree δG. Then,(6)γ3RG≤4pδG+1ln3δG+14+1.Theorem 9.
LetG be a graph of order n≥593 for which diamG and diamG¯ are equal to two. Then,(7)γ3RGγ3RG¯<292p.Proof.
LetG be a graph of order n≥452 with diamG=diamG¯=2, and suppose u is a vertex of minimum degree in G. If degu≤2, then the diameter constraint follows that VG−Nu,∅,∅,∅,Nu is a 3RDF for G and VG−Nu,∅,∅,Nu,u is a 3RDF of G¯, and so γ3RGγ3RG¯≤4Nu4+3Nu≤80<29/2p when n is greater than or equal to six. Hence, we can suppose that degu≥3, and similarly, δG¯ is greater than or equal to three.
LetM=VG−NGu. We choose a family of disjoint subsets of NGu dominating M as follows. Initialize U1=NGu; note that U1 dominates M; then, let Wi be a minimal subset of Ui dominating M, and let Ui+1=Ui−Wi. If Ui+1 does not dominate M, then stop setting q=i and W∗=Uq+1. Otherwise, repeat the process. Note that W1,W2,…,Wq is a partition of NGu−W∗, with each Wi being a minimal set that dominates M.
SinceWi is a minimal dominating set for M, there is a vertex si∈M having just one neighbor in Wi. Let ti be this neighbor. Since W∗ does not dominate M, there exists w∈M for which W∗⊆NG¯w. Let S=s1,s2,…,sq∪u,w and T=t1,t2,…,tq. Now, VG−S∪T,∅,∅,T,S is a 3RDF for G¯, since u dominates M, w dominates W∗, and ri dominates Wi−ti. Thus, γ3RG¯≤7q+8, which reduces to 7q+4 if W∗=∅.
LetU=Wj∪u, where Wj=minWi. Note that U is a dominating set for G. If U is equal to two, then γ3RG≤8. Since G¯ is connected and δG¯≥3, Theorem 1 yields γ3RG¯<7p/4 and then clearly γ3RGγ3RG¯<29/2p. Hence, we can suppose that U>2, which requires q≤δG/2. If q=1, then γ3RG¯≤15 and γ3RG≤4U≤4δG+1 and so γ3RGγ3RG¯≤60δG+1. Hence, we can suppose that δG≥29/120n−1, but now, Theorem 8 yields γ3RG≤480/29ln29/160n+1. Easily, it can be seen that 15.480/29ln29/160n+1<29p/2, when n≥58, and thus, γ3RGγ3RG¯<29/2p.
Hence, we can suppose that2≤q≤δG/2. Using the 3RDF VG−U,∅,∅,∅,U, we have(8)γ3RGγ3RG¯≤4δGq+4⋅7q+8=28δG+32+28q+32δGq≤28δG+32+31δG+27=59δ+59.
Since59δG+59<29p/2 when δG<29/118n−1, we can suppose that δG≥29/118n−1 and similarly δG¯≥29/118n−1. By Theorem 8, maxG3RG,γ3RG¯≤472/29ln87p−ln472+1. Hence, γ3RGγ3RG¯≤472/29ln87p−ln472+12, and this leads to the result since n≥593. □


## 3. New Bounds for the Triple Roman Domination Number of Trees

We establish some bounds on the triple Roman domination number of trees. For each treeT, let sT and ℓT denote the number of support vertices and leaves of T, respectively. We begin with some simple lemmas.Lemma 2.
Lett be a nonnegative integer, and let T be a rooted tree and v∈VT be a vertex different from its root. Then, we have the following:(1)
Ifγ3RT≤γ3RT−Tv+3/2nTv+t, γ3RT−Tv≤3nT−Tv+sT−Tv/2, and sT−Tv≤sT−2t, then γ3RT≤3nT+sT/2(2)
Ifγ3RT≥γ3RT−Tv+4/3nTv−4/3t, γ3RT−Tv≥⌈4nT−Tv+2−ℓT−Tv/3⌉, and ℓT−Tv≤ℓT−t, then γ3RT≥⌈4nT+2−ℓT/3⌉Observation 1.
LetT be a tree and y∈VT. If T′ is the tree obtained from T by adding a star K1,ss≥2 and joining y to one leaf of K1,s, then γ3RT′=γ3RT+4.Next, we improve the upper bound of Theorem1 for trees. Let ℱ be the family of all trees that can be built from k≥1 copies P4=v1iv2iv3iv4i1≤i≤k by adding k−1 edges between the vertices v12,v22,…,v2k to connect the graph.Theorem 10.
IfT is a tree of order n≥2, then(9)γ3RT≤3n+sT2.Furthermore, this bound is sharp for all trees inℱ.Proof.
We proceed by induction onn. If n≤4, then clearly γ3RT≤3n+sT/2. Suppose that n is greater than or equal to five, and let the result hold for all nontrivial trees of order less than n. Let T be a tree of order n≥5. If diamT is equal to two, then T is a star and we have γ3RT=4<3n+1/2. If diamT is greater than or equal to three, then T is a double star and we have γ3RT<3n/2+1=3n+sT/2. Henceforth, we suppose diamT is greater than or equal to four. Let v1v2,…,vkk≥5 be a diametral path in T for which degv2 is as large as possible and root T at vk. If degv2≥4, then γ3RT=γ3RT−v1; if degv3≥degv2=3, then γ3RT≤γ3RT−Tv2+4; and if 3=degv2>degv3, then γ3RT≤γ3RT−Tv3+4, and using the induction hypothesis and setting t=0 in Lemma 2-(1), we obtain γ3RT≤3n+sT/2 in all of the above cases. Suppose that degv2=2. By the choice of diametral path, we can suppose that all children of v3 with depth one have degree two.
Ifdegv3=2, then by Observation 1, we have γ3RT=γ3RT−Tv3+4, and by the induction hypothesis on T−Tv3 and setting t=0 in Lemma 2-(1), we have γ3RT≤3n+sT/2. Suppose that degv3≥3. If v3 is a strong support vertex or v3 is a support vertex and degv3≥4, then clearly γ3RT=γ3RT−Tv2+3, and using the induction hypothesis on T−Tv2 and setting t=0 in Lemma 2-(1), we have γ3RT≤3n+sT/2. Next, we consider the following cases:Case 1. v3 is a support vertex and degv3=3.IfdiamT=4, then the result is immediate. Suppose that diamT≥5. If degv4=2, then each γ3RT−Tv4-function can be extended to a 3RDF of T by assigning a 4 to v3, a 3 to v1, and a 0 to the other vertices of Tv4 following that γ3RT≤γ3RT−Tv4+7, and applying the induction hypothesis on T−Tv4 and setting t=1 in Lemma 2-(1), we obtain γ3RT≤3n+sT/2. Suppose that degv4≥3. Then, clearly sT−Tv3=sT−2 and as above, we have γ3RT≤γ3RT−Tv3+7, and using the induction hypothesis on T−Tv3 and setting t=0 in Lemma 2-(1), we have γ3RT≤3n+sT/2.Case 2. v3 is not a support vertex and degv3≥4.Then,Tv3 is a healthy spider with at least three feet. We first suppose that degv3≥5, then γ3RT=γ3RT−Tv2+3, and applying the induction hypothesis on T−Tv2 and setting t=0 in Lemma 2-(1), we have γ3RT≤3n+sT/2. Now, we suppose that degv3=4. If degv4=2, then each γ3RT−Tv4-function can be extended to a 3RDF of T by assigning a 4 to v3, a 3 to leaves of Tv4 except v4, and a 0 to the other vertices of Tv4 following that γ3RT≤γ3RT−Tv4+13, and applying the induction hypothesis on T−Tv4 and setting t=1 in Lemma 2-(1), we obtain γ3RT=3n+sT/2.Ifdegv4≥3, then each γ3RT−Tv3-function can be extended to a 3RDF of T by assigning a 3 to v3, a 3 to leaves of Tv3, and a 0 to the other vertices of Tv3 following that γ3RT≤γ3RT−Tv3+12, and applying the induction hypothesis on T−Tv3 we have γ3RT≤3n−7+sT−3/2+12=3n+sT/2.Case 3. v3 is not a support vertex and degv3=3.IfdiamT=4, then the result is immediate. Let diamT≥5 and sT−Tv3≤sT−1 and γ3RT≤γ3RT−Tv3+8 since each γ3RT−Tv3-function can be extended to a 3RDF of T by assigning a 0 to v3 and the leaves of Tv3 and a 4 to the children of v3. Using the induction hypothesis on T−Tv3, we have γ3RT≤3n−5+sT−1/2+8=3n+sT/2. This completes the proof. □
Now, we provide a lower bound on the triple Roman domination number of a treeT in terms of its order and the number of its leaves and support vertices.Theorem 11.
LetT be a tree of order n≥2 with ℓT leaves. Then,(10)γ3RT≥4nT+2−ℓT3.Furthermore, this bound is sharp for stars.Proof.
We proceed by induction onn. If n=2, then clearly γ3RT=4>⌈4nT+2−ℓT/3⌉, and if n=3, then the only tree T is P3 and clearly γ3RT=4=⌈43+2−2/3⌉. Suppose n≥4, and let the result hold for all nontrivial trees T of order at most n−1. Suppose T is a tree of order n≥4. If diameter T is equal to 2, then T is a star and γ3RT=4=⌈4n+2−n+1/3⌉. If diameter T is equal to 3, then T is a double star and we have γ3RT≥7>⌈4n+2−n+2/3⌉. Henceforth, we suppose diamT≥4. Let v1v2,…,vkk≥5 be a diametral path in T for which degv2 is as large as possible and root T at vk. Suppose l is a γ3RT-function of T for which lv2 is as large as possible. If degv2≥3, then clearly lv2=4 and so l is a triple Roman dominating function of T−v1. Since ℓT−v1=ℓT−1, applying the induction hypothesis on T−v1 and setting t=1 in Lemma 2-(2), we obtain γ3RT≥⌈4nT+2−ℓT/3⌉.
Suppose thatdegv2=2. By the choice of diametral path, we can suppose that each child of v3 with depth 1 has degree 2. We consider the following cases:Case 1. v3 has a child w with depth one different from v2 or v3 is a support vertex.LetT′=T−Tv2. If v3 has a child w with depth one different from v2, then we can suppose that lw≥lv2. Clearly, lv1+lv2≥3 and the function l, restricted to T′, is a triple Roman dominating function of T′, and this follows that γ3RT≥γ3RT′+3. Since ℓT′=ℓT−1<ℓT, using the induction hypothesis on T′ and setting t=0 in Lemma 2-(2), we have γ3RT>⌈4nT+2−ℓT/3⌉.Now, letv3 be a support vertex. It is obvious that lVTv3≥7. We can suppose that lv3=4 and lv1=3. Now, the result follows as above.Case 2.degv3=2.LetT′=T−Tv3. By Observation 5, we have γ3RT=γ3RT′+4. Since ℓT′≤ℓT, using the induction hypothesis on T−Tv3 and setting t=0 in Lemma 2-(2), we obtain γ3RT≥⌈4nT+2−ℓT/3⌉. □


## 4. Conclusion

The main objective of this paper was to study the triple Roman domination number in graphs. We first presented Nordhaus–Gaddum inequalities for the triple Roman domination number, and then, we focused on trees and proved that, for each treeT of order n≥2, γ3RT≤3n+sT/2 and γ3RT≥⌈4nT+2−ℓT/3⌉, where sT and ℓT are the number of support vertices and leaves of T. Characterizing trees attaining the bounds of Theorems 10 and 11 may be considered for future works.



---

*Source: 9992618-2022-01-04.xml*