New Bounds on the Triple Roman Domination Number of Graphs

Abstract

In this paper, we derive sharp upper and lower bounds on the sum ${\gamma }_{3R}G+{\gamma }_{3R}\overline{G}$ and product ${\gamma }_{3R}G{\gamma }_{3R}\overline{G}$, where $\overline{G}$ is the complement of graph $G$. We also show that for each tree $T$ of order $n\ge 2$, ${\gamma }_{3R}T\le 3n+sT/2$ and ${\gamma }_{3R}T\ge \lceil 4nT+2-\ell T/3\rceil$, where $sT$ and $\ell T$ are the number of support vertices and leaves of $T$.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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\in VG|uv\in EG$, and the closed neighborhood of $v$ is the set $Nv=Nv\cup v$. The degree of a vertex $v\in V$ is ${\text{deg}}_{G}v=\text{deg}v=Nv$. The minimum and maximum degree of a graph $G$ are denoted by $\delta G=\delta$ and $\mathrm{\Delta }G=\mathrm{\Delta }$, respectively. The complement of a graph is denoted by $\overline{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 $T_v$.

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.

Let $k\ge 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:=\mathrm{0,1,2},\dots ,k+1$ to the vertices of a graph $G$. For a vertex $v\in VG$, the active neighborhood of $v$, denoted by $\text{AN}v$, is the set of vertices $w\in N_{G}v$ such that $fw\ge 1$. A $k$-RDF is a function $f:VG⟶S$ satisfying the condition that for any vertex $v\in VG$ with $fv<k,f{N}_{G}v\ge \text{AN}v+k$. The weight of a $k$-RDF is $\omega f={\mathrm{\Sigma }}_{v\in VG}fv$. The $k$-Roman domination number ${\gamma }_{kR}G$ 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 $\rho$, bounds for the sum $\rho G+\rho \overline{G}$ or product $\rho G\times \rho \overline{G}$ are called results of “Nordhaus–Gaddum” type, honoring the paper of Nordhaus–Gaddum [15] obtaining such bounds when $\rho$ is the chromatic number.

In this paper, we first present Nordhaus–Gaddum-type bounds for the triple Roman domination number. For each tree $T$ of order $n\ge 2$, we also show that ${\gamma }_{3R}T\le 3n+sT/2$ and ${\gamma }_{3R}T\ge \lceil 4nT+2-\ell T/3\rceil$.

We will use the next results in this paper. Let $\mathrm{ℱ}$ be the family of all trees that can be built from k ≥ 1 paths $P_4=v_1^i{v}_2^i{v}_3^i{v}_4^{i}1\le i\le k$ by adding k − 1 edges incident with the $v_2^i$’s, so that they induce a connected subgraph. (see Figure 1).

[figure omitted; refer to PDF]

Theorem 1.

For any connected graph $G$ of order $n\ge 2$, ${\gamma }_{3R}G\le 7n/4$ with equality if and only if $G\in \mathrm{ℱ}$.

Theorem 2.

For each connected graph $G$, there exists a ${\gamma }_{3R}G$-function that does not value the label one to each vertex in $G$.

Theorem 3.

Let $G$ be a connected graph on $n\ge 1$ vertices. Then, ${\gamma }_{3R}G=3$ if and only if $G=K_1$.

Theorem 4.

If $G$ is a connected graph on $n\ge 2$ vertices, then ${\gamma }_{3R}G=4$ if and only if $\mathrm{\Delta }=n-1$.

Theorem 5.

There is no connected graph of order $n$ for which ${\gamma }_{3R}G=5$.

Theorem 6.

If $G$ is a connected graph on $n$ vertices, then ${\gamma }_{3R}G=6$ if and only if there are two nonjoin vertices in $VG$ with degree $\mathrm{\Delta }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.

If $G$ is a graph of order $n$ and maximum degree $\mathrm{\Delta }G$, then$$\begin{array}{}\text{(1)}& {\gamma }_{3R}G\le 3n-3\Delta G+1.\end{array}$$

Moreover, if $\mathrm{\Delta }G<n-1$ and ${\gamma }_{3R}G=3n-3\mathrm{\Delta }G+1$, then ${\gamma }_{3R}\overline{G}\le 1+3\mathrm{\Delta }G$.

Proof.

Suppose $b$ is a vertex of maximum degree $\mathrm{\Delta }$. Clearly $Nb,\varnothing ,\varnothing ,VG-Nb,b$ is a 3RD-function of weight $3n-3\mathrm{\Delta }+1$ and so ${\gamma }_{3R}G\le 3n-3\mathrm{\Delta }+1$.

Let $\mathrm{\Delta }G<n-1$ and ${\gamma }_{3R}G=3n-3\mathrm{\Delta }+1$. Let $b\in VG$ be a vertex with maximum degree $\mathrm{\Delta }G$, and let $B=VG-Nb$. Suppose that $z\in B$ is a vertex with maximum degree in $GB$. If $u$ has a neighbor in $B$, then the function $l=Nz\cup Nb,\varnothing ,\varnothing ,VG-Nb\cup Nz,z,b$ is a 3RD-function of $G$ of weight smaller than ${\gamma }_{3R}G$, a contradiction. Therefore, $\mathrm{\Delta }GB=0$. If $Nb=Nz$, then $Nb,\varnothing ,\varnothing ,VG-Nb,\varnothing$ is a 3RD-function of $G$ of weight $3n-3\mathrm{\Delta }G$ which is a contradiction. Hence, there is a vertex $t\in Nb$ for which $zt\notin EG$. Then, $B-z\cup b,t,\varnothing ,\varnothing ,Nb-t,z$ is a 3RDF of $\overline{G}$ of weight $3\mathrm{\Delta }-1+4$ as desired. $\square$

Theorem 7.

If $G$ is a graph of order $n$ and $n\ge 2$, then$$\begin{array}{}\text{(2)}& 10\le {\gamma }_{3R}G+{\gamma }_{3R}\overline{G}\le 3n+4.\end{array}$$

Equality holds for the lower bound if and only if $G$ or $\overline{G}$ is $K_2$, and equality holds for the upper bound if and only if $G$ or $\overline{G}$ is a complete graph.

Proof.

We can suppose that ${\gamma }_{3R}G\le {\gamma }_{3R}\overline{G}$. First, we show the left inequality. If ${\gamma }_{3R}G\ge 6$, then ${\gamma }_{3R}G+{\gamma }_{3R}\overline{G}\ge 12$ as desired. Let ${\gamma }_{3R}G\le 5$. By Theorems 3 and 5, we find ${\gamma }_{3R}G=4$, and Theorem 4 follows that $\mathrm{\Delta }G=n-1$. Hence, $\overline{G}$ is disconnected and so ${\gamma }_{3R}\overline{G}\ge 6$. Thus, ${\gamma }_{3R}G+{\gamma }_{3R}\overline{G}\ge 10$. If the equality holds, then we should have ${\gamma }_{3R}\overline{G}=6$. As noted, $G$ has a vertex of degree $n-1$, say $b$. Since $b$ is an isolated vertex in $\overline{G}$, we find that $n=2$ and, consequently, $G=K_2$.

Next, we show the upper bound. By Lemma 1, we find ${\gamma }_{3R}G\le 3n-3\mathrm{\Delta }G+1$ and ${\gamma }_{3R}\overline{G}\le 3n-3\mathrm{\Delta }\overline{G}+1$. If ${\gamma }_{3R}G\le 3n-3\mathrm{\Delta }G$ and ${\gamma }_{3R}\overline{G}\le 3n-3\mathrm{\Delta }\overline{G}$, then we find$$\begin{array}{c}\text{(3)}& {\gamma }_{3R}G+{\gamma }_{3R}\overline{G}\le 3n-3\Delta G+3n-3\Delta \overline{G}=3n-3\Delta G+3\delta G+3\\ \le 3n+1.\end{array}$$

Suppose that ${\gamma }_{3R}G=3n-3\mathrm{\Delta }G+1$. If $\mathrm{\Delta }G<n-1$, then Lemma 1 follows that ${\gamma }_{3R}\overline{G}\le 1+3\mathrm{\Delta }G$ and so$$\begin{array}{c}\text{(4)}& {\gamma }_{3R}G+{\gamma }_{3R}\overline{G}\le 3n-3\Delta G+1+3\Delta G+1\le 3n+2.\end{array}$$

Suppose $\mathrm{\Delta }G=n-1$. Then, we have ${\gamma }_{3R}G$ is equal to four. If $\mathrm{\Delta }\overline{G}\ge 1$, then we have$$\begin{array}{c}\text{(5)}& {\gamma }_{3R}G+{\gamma }_{3R}\overline{G}\le 4+3n-3\Delta \overline{G}+1\le 3n+2.\end{array}$$

Suppose that $\mathrm{\Delta }\overline{G}=0$. Then, $G$ is complete graph, and clearly, we have ${\gamma }_{3R}G+{\gamma }_{3R}\overline{G}=3n+4$. This completes the proof. $\square$

To prove an upper bound on the product ${\gamma }_{3R}G{\gamma }_{3R}\overline{G}$, we use the following result in [13].

Theorem 8.

Let $G$ be a graph of order $n$ and minimum degree $\delta G$. Then,$$\begin{array}{}\text{(6)}& {\gamma }_{3R}G\le \frac{4p}{\delta G+1}\text{ln}\frac{3\delta G+1}{4}+1.\end{array}$$

Theorem 9.

Let $G$ be a graph of order $n\ge 593$ for which $\text{diam}G$ and $\text{diam}\overline{G}$ are equal to two. Then,$$\begin{array}{}\text{(7)}& {\gamma }_{3R}G{\gamma }_{3R}\overline{G}<\frac{29}{2}p.\end{array}$$

Proof.

Let $G$ be a graph of order $n\ge 452$ with $\text{diam}G=\text{diam}\overline{G}=2$, and suppose $u$ is a vertex of minimum degree in $G$. If $\text{deg}u\le 2$, then the diameter constraint follows that $VG-Nu,\varnothing ,\varnothing ,\varnothing ,Nu$ is a 3RDF for $G$ and $VG-Nu,\varnothing ,\varnothing ,Nu,u$ is a 3RDF of $\overline{G}$, and so ${\gamma }_{3R}G{\gamma }_{3R}\overline{G}\le 4Nu4+3Nu\le 80<29/2p$ when $n$ is greater than or equal to six. Hence, we can suppose that $\text{deg}u\ge 3$, and similarly, $\delta \overline{G}$ is greater than or equal to three.

Let $M=VG-N_{G}u$. We choose a family of disjoint subsets of $N_{G}u$ dominating $M$ as follows. Initialize $U_1=N_{G}u$; note that $U_1$ dominates $M$; then, let $W_i$ be a minimal subset of $U_i$ dominating $M$, and let $U_{i+1}=U_i-W_i$. If $U_{i+1}$ does not dominate $M$, then stop setting $q=i$ and $W^{\ast }=U_{q+1}$. Otherwise, repeat the process. Note that $W_1,W_2,\dots ,W_q$ is a partition of $N_{G}u-W^{\ast }$, with each $W_i$ being a minimal set that dominates $M$.

Since $W_i$ is a minimal dominating set for $M$, there is a vertex $s_i\in M$ having just one neighbor in $W_i$. Let $t_i$ be this neighbor. Since $W^{\ast }$ does not dominate $M$, there exists $w\in M$ for which $W^{\ast }\subseteq N_{\overline{G}}w$. Let $S=s_1,s_2,\dots ,s_q\cup u,w$ and $T=t_1,t_2,\dots ,t_q$. Now, $VG-S\cup T,\varnothing ,\varnothing ,T,S$ is a 3RDF for $\overline{G}$, since $u$ dominates $M$, $w$ dominates $W^{\ast }$, and $r_i$ dominates $W_i-t_i$. Thus, ${\gamma }_{3R}\overline{G}\le 7q+8$, which reduces to $7q+4$ if $W^{\ast }=\varnothing$.

Let $U=W_j\cup u$, where $W_j=\text{min}{W}_i$. Note that $U$ is a dominating set for $G$. If $U$ is equal to two, then ${\gamma }_{3R}G\le 8$. Since $\overline{G}$ is connected and $\delta \overline{G}\ge 3$, Theorem 1 yields ${\gamma }_{3R}\overline{G}<7p/4$ and then clearly ${\gamma }_{3R}G{\gamma }_{3R}\overline{G}<29/2p$. Hence, we can suppose that $U>2$, which requires $q\le \delta G/2$. If $q=1$, then ${\gamma }_{3R}\overline{G}\le 15$ and ${\gamma }_{3R}G\le 4U\le 4\delta G+1$ and so ${\gamma }_{3R}G{\gamma }_{3R}\overline{G}\le 60\delta G+1$. Hence, we can suppose that $\delta G\ge 29/120n-1$, but now, Theorem 8 yields ${\gamma }_{3R}G\le 480/29\text{ln}29/160n+1$. Easily, it can be seen that $15.480/29\text{ln}29/160n+1<29p/2$, when $n\ge 58$, and thus, ${\gamma }_{3R}G{\gamma }_{3R}\overline{G}<29/2p$.

Hence, we can suppose that $2\le q\le \delta G/2$. Using the 3RDF $VG-U,\varnothing ,\varnothing ,\varnothing ,U$, we have$$\begin{array}{c}\text{(8)}& {\gamma }_{3R}G{\gamma }_{3R}\overline{G}\le \frac{4\delta G}{q}+4\cdot 7q+8=28\delta G+32+28q+\frac{32\delta G}{q}\\ \le 28\delta G+32+31\delta G+27\\ =59\delta +59.\end{array}$$

Since $59\delta G+59<29p/2$ when $\delta G<29/118n-1$, we can suppose that $\delta G\ge 29/118n-1$ and similarly $\delta \overline{G}\ge 29/118n-1$. By Theorem 8, $\max G_{3R}G,{\gamma }_{3R}\overline{G}\le 472/29\ln 87p-\ln 472+1$. Hence, ${\gamma }_{3R}G{\gamma }_{3R}\overline{G}\le {472/29\ln 87p-\ln 472+1}^2$, and this leads to the result since $n\ge 593$. $\square$

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 tree $T$, let $sT$ and $\ell T$ denote the number of support vertices and leaves of $T$, respectively. We begin with some simple lemmas.

Lemma 2.

Let $t$ be a nonnegative integer, and let $T$ be a rooted tree and $v\in VT$ be a vertex different from its root. Then, we have the following:

(1) If ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_v+3/2n{T}_v+t$, ${\gamma }_{3R}T-T_v\le 3nT-T_v+sT-T_v/2$, and $sT-T_v\le sT-2t$, then ${\gamma }_{3R}T\le 3nT+sT/2$

(2) If ${\gamma }_{3R}T\ge {\gamma }_{3R}T-T_v+4/3n{T}_v-4/3t$, ${\gamma }_{3R}T-T_v\ge \lceil 4nT-T_v+2-\ell T-T_v/3\rceil$, and $\ell T-T_v\le \ell T-t$, then ${\gamma }_{3R}T\ge \lceil 4nT+2-\ell T/3\rceil$

Observation 1.

Let $T$ be a tree and $y\in VT$. If $T^{\prime }$ is the tree obtained from $T$ by adding a star $K_{1,s}s\ge 2$ and joining $y$ to one leaf of $K_{1,s}$, then ${\gamma }_{3R}{T}^{\prime }={\gamma }_{3R}T+4$.

Next, we improve the upper bound of Theorem 1 for trees. Let $\mathrm{ℱ}$ be the family of all trees that can be built from $k\ge 1$ copies $P_4=v_1^i{v}_2^i{v}_3^i{v}_4^{i}1\le i\le k$ by adding $k-1$ edges between the vertices $v_1^2,v_2^2,\dots ,v_2^k$ to connect the graph.

Theorem 10.

If $T$ is a tree of order $n\ge 2$, then$$\begin{array}{}\text{(9)}& {\gamma }_{3R}T\le \frac{3n+sT}{2}.\end{array}$$

Furthermore, this bound is sharp for all trees in $\mathrm{ℱ}$.

Proof.

We proceed by induction on $n$. If $n\le 4$, then clearly ${\gamma }_{3R}T\le 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\ge 5$. If $\text{diam}T$ is equal to two, then $T$ is a star and we have ${\gamma }_{3R}T=4<3n+1/2$. If $\text{diam}T$ is greater than or equal to three, then $T$ is a double star and we have ${\gamma }_{3R}T<3n/2+1=3n+sT/2$. Henceforth, we suppose $\text{diam}T$ is greater than or equal to four. Let $v_1{v}_2,\dots ,v_{k}k\ge 5$ be a diametral path in $T$ for which $\text{deg}{v}_2$ is as large as possible and root $T$ at $v_k$. If $\text{deg}{v}_2\ge 4$, then ${\gamma }_{3R}T={\gamma }_{3R}T-v_1$; if $\text{deg}{v}_3\ge \text{deg}{v}_2=3$, then ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_{v_2}+4$; and if $3=\text{deg}{v}_2>\text{deg}{v}_3$, then ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_{v_3}+4$, and using the induction hypothesis and setting $t=0$ in Lemma 2-(1), we obtain ${\gamma }_{3R}T\le 3n+sT/2$ in all of the above cases. Suppose that $\text{deg}{v}_2=2$. By the choice of diametral path, we can suppose that all children of $v_3$ with depth one have degree two.

If $\text{deg}{v}_3=2$, then by Observation 1, we have ${\gamma }_{3R}T={\gamma }_{3R}T-T_{v_3}+4$, and by the induction hypothesis on $T-T_{v_3}$ and setting $t=0$ in Lemma 2-(1), we have ${\gamma }_{3R}T\le 3n+sT/2$. Suppose that $\text{deg}{v}_3\ge 3$. If $v_3$ is a strong support vertex or $v_3$ is a support vertex and $\text{deg}{v}_3\ge 4$, then clearly ${\gamma }_{3R}T={\gamma }_{3R}T-T_{v_2}+3$, and using the induction hypothesis on $T-T_{v_2}$ and setting $t=0$ in Lemma 2-(1), we have ${\gamma }_{3R}T\le 3n+sT/2$. Next, we consider the following cases:

  Case 1. $v_3$ is a support vertex and $\text{deg}{v}_3=3$.

  If $\text{diam}T=4$, then the result is immediate. Suppose that $\text{diam}T\ge 5$. If $\text{deg}{v}_4=2$, then each ${\gamma }_{3R}T-T_{v_4}$-function can be extended to a 3RDF of $T$ by assigning a 4 to $v_3$, a 3 to $v_1$, and a 0 to the other vertices of $T_{v_4}$ following that ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_{v_4}+7$, and applying the induction hypothesis on $T-T_{v_4}$ and setting $t=1$ in Lemma 2-(1), we obtain ${\gamma }_{3R}T\le 3n+sT/2$. Suppose that $\text{deg}{v}_4\ge 3$. Then, clearly $sT-T_{v_3}=sT-2$ and as above, we have ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_{v_3}+7$, and using the induction hypothesis on $T-T_{v_3}$ and setting $t=0$ in Lemma 2-(1), we have ${\gamma }_{3R}T\le 3n+sT/2$.

  Case 2. $v_3$ is not a support vertex and $\text{deg}{v}_3\ge 4$.

  Then, $T_{v_3}$ is a healthy spider with at least three feet. We first suppose that $\text{deg}{v}_3\ge 5$, then ${\gamma }_{3R}T={\gamma }_{3R}T-T_{v_2}+3$, and applying the induction hypothesis on $T-T_{v_2}$ and setting $t=0$ in Lemma 2-(1), we have ${\gamma }_{3R}T\le 3n+sT/2$. Now, we suppose that $\text{deg}{v}_3=4$. If $\text{deg}{v}_4=2$, then each ${\gamma }_{3R}T-T_{v_4}$-function can be extended to a 3RDF of $T$ by assigning a 4 to $v_3$, a 3 to leaves of $T_{v_4}$ except $v_4$, and a 0 to the other vertices of $T_{v_4}$ following that ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_{v_4}+13$, and applying the induction hypothesis on $T-T_{v_4}$ and setting $t=1$ in Lemma 2-(1), we obtain ${\gamma }_{3R}T=3n+sT/2$.

  If $\text{deg}{v}_4\ge 3$, then each ${\gamma }_{3R}T-T_{v_3}$-function can be extended to a 3RDF of $T$ by assigning a 3 to $v_3$, a 3 to leaves of $T_{v_3}$, and a 0 to the other vertices of $T_{v_3}$ following that ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_{v_3}+12$, and applying the induction hypothesis on $T-T_{v_3}$ we have ${\gamma }_{3R}T\le 3n-7+sT-3/2+12=3n+sT/2$.

  Case 3. $v_3$ is not a support vertex and $\text{deg}{v}_3=3$.

  If $\text{diam}T=4$, then the result is immediate. Let $\text{diam}T\ge 5$ and $sT-T_{v_3}\le sT-1$ and ${\gamma }_{3R}T\le {\gamma }_{3R}T-T_{v_3}+8$ since each ${\gamma }_{3R}T-T_{v_3}$-function can be extended to a 3RDF of $T$ by assigning a 0 to $v_3$ and the leaves of $T_{v_3}$ and a 4 to the children of $v_3$. Using the induction hypothesis on $T-T_{v_3}$, we have ${\gamma }_{3R}T\le 3n-5+sT-1/2+8=3n+sT/2$. This completes the proof. $\square$

Now, we provide a lower bound on the triple Roman domination number of a tree $T$ in terms of its order and the number of its leaves and support vertices.

Theorem 11.

Let $T$ be a tree of order $n\ge 2$ with $\ell T$ leaves. Then,$$\begin{array}{}\text{(10)}& {\gamma }_{3R}T\ge \frac{4nT+2-\ell T}{3}.\end{array}$$

Furthermore, this bound is sharp for stars.

Proof.

We proceed by induction on $n$. If $n=2$, then clearly ${\gamma }_{3R}T=4>\lceil 4nT+2-\ell T/3\rceil$, and if $n=3$, then the only tree $T$ is $P_3$ and clearly ${\gamma }_{3R}T=4=\lceil 43+2-2/3\rceil$. Suppose $n\ge 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\ge 4$. If diameter $T$ is equal to 2, then $T$ is a star and ${\gamma }_{3R}T=4=\lceil 4n+2-n+1/3\rceil$. If diameter $T$ is equal to 3, then $T$ is a double star and we have ${\gamma }_{3R}T\ge 7>\lceil 4n+2-n+2/3\rceil$. Henceforth, we suppose $\text{diam}T\ge 4$. Let $v_1{v}_2,\dots ,v_{k}k\ge 5$ be a diametral path in $T$ for which $\text{deg}{v}_2$ is as large as possible and root $T$ at $v_k$. Suppose $l$ is a ${\gamma }_{3R}T$-function of $T$ for which $l{v}_2$ is as large as possible. If $\text{deg}{v}_2\ge 3$, then clearly $l{v}_2=4$ and so $l$ is a triple Roman dominating function of $T-v_1$. Since $\ell T-v_1=\ell T-1$, applying the induction hypothesis on $T-v_1$ and setting $t=1$ in Lemma 2-(2), we obtain ${\gamma }_{3R}T\ge \lceil 4nT+2-\ell T/3\rceil$.

Suppose that $\text{deg}{v}_2=2$. By the choice of diametral path, we can suppose that each child of $v_3$ with depth 1 has degree 2. We consider the following cases:

  Case 1. $v_3$ has a child $w$ with depth one different from $v_2$ or $v_3$ is a support vertex.

  Let $T^{\prime }=T-T_{v_2}$. If $v_3$ has a child $w$ with depth one different from $v_2$, then we can suppose that $lw\ge l{v}_2$. Clearly, $l{v}_1+l{v}_2\ge 3$ and the function $l$, restricted to $T^{\prime }$, is a triple Roman dominating function of $T^{\prime }$, and this follows that ${\gamma }_{3R}T\ge {\gamma }_{3R}{T}^{\prime }+3$. Since $\ell T^{\prime }=\ell T-1<\ell T$, using the induction hypothesis on $T^{\prime }$ and setting $t=0$ in Lemma 2-(2), we have ${\gamma }_{3R}T>\lceil 4nT+2-\ell T/3\rceil$.

  Now, let $v_3$ be a support vertex. It is obvious that $lV{T}_{v_3}\ge 7$. We can suppose that $l{v}_3=4$ and $l{v}_1=3$. Now, the result follows as above.

  Case 2.$\text{deg}{v}_3=2$.

  Let $T^{\prime }=T-T_{v_3}$. By Observation 5, we have ${\gamma }_{3R}T={\gamma }_{3R}{T}^{\prime }+4$. Since $\ell T^{\prime }\le \ell T$, using the induction hypothesis on $T-T_{v_3}$ and setting $t=0$ in Lemma 2-(2), we obtain ${\gamma }_{3R}T\ge \lceil 4nT+2-\ell T/3\rceil$. $\square$

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 tree $T$ of order $n\ge 2$, ${\gamma }_{3R}T\le 3n+sT/2$ and ${\gamma }_{3R}T\ge \lceil 4nT+2-\ell T/3\rceil$, where $sT$ and $\ell 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.

Acknowledgments

H. Abdollahzadeh Ahangar was supported by the Babol Noshirvani University of Technology under research grant number BNUT/385 001/00.

References

[1] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, 1998.

[2] A. M. Hanan Ahmed, A. Alwardi, M. R. Sakestina, "On domination topological indices of graphs," International Journal of Analysis and Applications, vol. 19, pp. 47-64, 2021.

[3] S. Bermudo, J. E. Nápoles, J. Rada, "Extremal trees for the Randić index with given domination number," Applied Mathematics and Computation, vol. 375,DOI: 10.1016/j.amc.2020.125122, 2020.

[4] B. Borovićanin, B. Furtula, "On extremal Zagreb indices of trees with given domination number," Applied Mathematics and Computation, vol. 279, pp. 208-218, 2016.

[5] P. Dankelmann, "Average distance and domination number," Discrete Applied Mathematics, vol. 80 no. 1, pp. 21-35, DOI: 10.1016/s0166-218x(97)00067-x, 1997.

[6] A. A. S. Ahmad Jamri, R. Hasni, S. Kartini Said Husain, "On the Zagreb indices of graphs with given Roman domination number," Communications in Combinatorics and Optimization, . To appear

[7] A. A. S. Ahmad Jamri, F. Movahedi, R. Hasni, M. H. Akhbari, A note on the lower bound of the seconed Zagreb index of trees with a given domination number, . Communications in Combinatorics and Optimization, to appear

[8] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi, S. T. Hedetniemi, "Roman domination in graphs," Discrete Mathematics, vol. 278 no. 1-3, pp. 11-22, DOI: 10.1016/j.disc.2003.06.004, 2004.

[9] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, S. M. Sheikholeslami, "Total Roman reinforcement in graphs," Discussiones Mathematicae Graph Theory, vol. 39 no. 4, pp. 787-803, DOI: 10.7151/dmgt.2108, 2019.

[10] F. Azvin, N. Jafari Rad, L. Volkmann, "Bounds on the outer-independent double Italian domination number," Communications in Combinatorics and Optimization, vol. 6, pp. 123-136, 2021.

[11] R. A. Beeler, T. W. Haynes, S. T. Hedetniemi, "Double Roman domination," Discrete Applied Mathematics, vol. 211, pp. 23-29, DOI: 10.1016/j.dam.2016.03.017, 2016.

[12] L. Volkmann, "Double Roman domination and domatic numbers of graphs," Communications in Combinatorics and Optimization, vol. 3, pp. 71-77, 2018.

[13] H. Abdollahzadeh Ahangar, M. P. Alvarez, M. Chellali, S. M. Sheikholeslami, J. C. Valenzuela-Tripodoro, "Triple Roman domination in graphs," Applied Mathematics and Computation, vol. 391 no. 13,DOI: 10.1016/j.amc.2020.125444, 2021.

[14] M. Hajjari, H. Abdollahzadeh Ahangar, R. Khoeilar, Z. Shao, S. M. Sheikholeslami, "An upper bound on triple Roman domination," Journal of Combinatorial Mathematics and Combinatorial Computing, . To appear

[15] E. A. Nordhaus, J. W. Gaddum, "On complementary graphs," The American Mathematical Monthly, vol. 63 no. 3, pp. 175-177, DOI: 10.2307/2306658, 1956.