Quasi total double Roman domination in graphs

Abstract

A quasi total double Roman dominating function (QTDRD-function) on a graph $G=(V(G),E(G))$ is a function $f:V(G)\to \{0,1,2,3\}$ having the property that (i) if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3; (ii) if f(v) = 1, then vertex v has at least one neighbor w with $f(w)\ge 2$, and (iii) if x is an isolated vertex in the subgraph induced by the set of vertices assigned nonzero values, then f(x) = 2. The weight of a QTDRD-function f is the sum of its function values over the whole vertices, and the quasi total double Roman domination number ${\gamma }_{\mathit{\text{qtdR}}}(G)$ equals the minimum weight of a QTDRD-function on G. In this paper, we first show that the problem of computing the quasi total double Roman domination number of a graph is NP-hard, and then we characterize graphs G with small or large ${\gamma }_{\mathit{\text{qtdR}}}(G)$. Moreover, we establish an upper bound on the quasi total double Roman domination number and we characterize the connected graphs attaining this bound.

KEYWORDS:

• Quasi total double Roman domination
• total double Roman domination
• double Roman domination number
• Roman domination number

MATHEMATICS SUBJECT CLASSIFICATION:

• 05C69

1 Introduction

All graphs considered in this article are finite, undirected, simple and without isolated vertices. Let $G=(V(G),E(G))$ be a graph of order $|V(G)|=n$. For any vertex $v\in V(G)$, the open neighbourhood of v is the set $N(v)=\{u\in V|\mathit{\text{uv}}\in E(G)\}$ and the closed neighbourhood of v is the set $N[v]=N(v)\cup \left\{v\right\}$. For a set $S\subseteq V$, the open neighbourhood of S is $N(S)=\underset{v\in S}{\cup }N(v)$ and the closed neighbourhood of S is $N[S]=N(S)\cup S$.

We denote the degree of a vertex v in a graph G by ${\mathrm{\text{deg}}}_G(v)$, or simply by $\mathrm{\text{deg}}(v)$ if the graph G is clear from the context. Let $\delta (G)$ and $\Delta (G)$ denote the minimum and maximum degree of vertices in G, respectively.

As usual a path, cycle, star and complete graph on n vertices are denoted by P_n, C_n, $K_{1,n-1}$ and K_n while $K_{n,m}$ and $D{S}_{p,q}$ denote the complete bipartite graph and double star of order m + n and $p+q+2$, respectively. A vertex of degree one is called a leaf and its neighbor a support vertex. A tree is an acyclic connected graph. For any integers $r\ge 0$ and $t\ge 0$ with $r+t\ge 1$, let $F_{r,t}$ be a tree obtained from a star $K_{1,r+t}$ by subdividing t edges exactly once. We say $F_{r,t}$ is a wounded spider if $r\ge 1$ and $t\ge 0$ and it is a healthy spider if r = 0 and $t\ge 2$. The center vertex of $F_{r,t}$ is also called the head vertex and the vertex at distance two from the head is called the foot vertex. Moreover, the leaf adjacent to the head vertex is called the wounding vertex. A path joining two vertices u and v is called a (u, v)-path. The diameter of a connected graph G, denoted by diam $(G),$ is the length of a shortest path between the most distanced vertices in G. A diametral path of a graph G is a shortest path whose length equals diam $(G).$ A rooted tree T distinguishes one vertex r called the root. For each $v\ne r$ of T, the parent of v is the neighbor of v on the unique (r, v)-path, while a child of v is any other neighbor of v. A descendant of v is a vertex $u\ne v$ such that the unique (r, u)-path contains v. For a vertex v in a rooted tree T, the maximal subtree at v is subtree of T induced by v and its descendants, and is denoted by T_v. The depth of v is the largest distance from v to a descendant of v. Recall that the corona cor(G) of a graph G is the graph obtained from G by adding for each vertex $v\in V(G)$a new vertex $v^{\prime }$ and the edge $v{v}^{\prime }$.

Roman domination is a variation of domination that was formally introduced in graph theory, by Cockayne et al. [11] in 2004. Since then, the topic has been widely studied, with over 250 papers have been published on it and its variations. For more details on Roman domination and its variants, we refer the reader to the book chapters [6, 7] and surveys [8–10].

In 2016, Beeler et al. defined a new variant of Roman domination in [3], namely double Roman dominating functions. A function $f:V(G)\to \{0,1,2,3\}$ is a double Roman dominating function(DRD-function) on a graph G if the following conditions hold: (i) If f(v) = 0, then v must have one neighbor assigned 3 or two neighbors each assigned 2, and (ii) If f(v) = 1, then v must have at least one neighbor w with $f(w)\ge 2$. The double Roman domination number ${\gamma }_{\mathit{\text{dR}}}(G)$ equals the minimum weight of a DRD-function on G. A DRD-function of G with weight ${\gamma }_{\mathit{\text{dR}}}(G)$ is called a ${\gamma }_{\mathit{\text{dR}}}(G)$-function or ${\gamma }_{\mathit{\text{dR}}}$-function of G. For a DRD-function f, let V_i be the set of vertices assigned the value i, where $i\in \{0,1,2,3\}.$ In that case, the function f will simply be referred to $f=(V_0,V_1,V_2,V_3).$ For more details on double Roman domination and its variations, see for example [1, 17, 20].

In 2020, Hao et al. [13] considered DRD-functions f such that the subgraph of G induced by the set $\{v\in V|f(v)\ge 1\}$ has no isolated vertices, and call such functions total double Roman dominating functions, TDRD-functions. The total double Roman domination number ${\gamma }_{\mathit{\text{tdR}}}(G)$ is the minimum weight of a TDRD-function on G. For more details, see also [14, 18, 19].

In this paper, we are interested in initiating the study of quasi total double Roman domination. A quasi total double Roman dominating function (QTDRD-function) on a graph G is a DRD-function with the additional condition that if x is an isolated vertex in the subgraph induced by the set of vertices labeled with 1, 2, and 3, then f(x) = 2. The minimum weight of a QTDRD-function on G is called the quasi total double Roman domination number of G and is denoted by ${\gamma }_{\mathit{\text{qtdR}}}(G)$. It is quite straightforward to note that any TDRD-function on G is a QTDRD-function leading to (1) $${\gamma }_{\mathit{\text{dR}}}(G)\le {\gamma }_{\mathit{\text{qtdR}}}(G)\le {\gamma }_{\mathit{\text{tdR}}}(G).$$(1)

It is worth mentioning that the quasi total version for Roman dominating functions has been introduced by Cabrera Martínez et al. [4] and has been further studied in [5, 12, 16].

In the rest of this paper, we begin the study of some combinatorial and computational properties of QTDRD-functions. We show that the problem of determining the quasi total double Roman domination number is NP-complete for bipartite graphs. Then we characterize graphs with small and large ${\gamma }_{\mathit{\text{qtdR}}}(G)$ and finally, we establish an upper bound on the quasi total double Roman domination number.

We end this section by determining the exact values of the quasi total double Roman domination number for paths and cycles. For this purpose we use the following results that can be found in [1].

Proposition 1.

For $n\ge 2$, $${\gamma }_{\mathit{\text{dR}}}(P_n)=\{\begin{array}{ccc}n\hfill & \text{if}\hfill & n\equiv 0\hspace{1em}\left(\mathrm{\text{mod}}3\right)\hfill \\ n+1\hfill & \hfill & \text{otherwise}.\hfill \end{array}$$

Moreover, the function f defined by $f(v_{3i+2})=3$ for $0\le i\le \frac{n-3}{3}$ and f(x) = 0 for the remaining vertices, is the unique ${\gamma }_{\mathit{\text{dR}}}(P_n)$-function when $n\equiv 0\hspace{1em}(\mathrm{\text{mod}}3)$.

Proposition 2.

For $n\ge 3$, $${\gamma }_{\mathit{\text{dR}}}(C_n)=\{\begin{array}{ccc}n\hfill & \text{if}\hfill & n\equiv 0,2,3,4,\hspace{1em}\left(\mathrm{\text{mod}}6\right)\hfill \\ n+1\hfill & \text{if}\hfill & n\equiv 1,5\hspace{1em}\left(\mathrm{\text{mod}}6\right).\hfill \end{array}$$

Moreover, the functions f_j defined by $f_j(v_{3i+j})=3$ for $0\le i\le \frac{n-3}{3}$ and $f_j(x)=0$ for the remaining vertices, for $j\in \{1,2,3\}$, are the only ${\gamma }_{\mathit{\text{dR}}}(C_n)$-functions when $n\equiv 3\hspace{1em}(\mathrm{\text{mod}}6)$.

Theorem 3.

For $n\ge 2,{\gamma }_{\mathit{\text{qtdR}}}(P_n)=n+1.$

Proof.

Let $P:=v_1{v}_2\dots v_n$ be a path of order n. Define the function h on $V(P_n)$ by $h(v_{2i-1})=2$ for $1\le i\le \frac{n+1}{2}$ and h(x) = 0 otherwise if n is odd and by $h(v_n)=1,h(v_{2i-1})=2$ for $1\le i\le \frac{n}{2}$ and h(x) = 0 for other vertices x, when n is even. It is easy to verify that h is a QTDRD-function of P_n of weight n + 1, leading to ${\gamma }_{\mathit{\text{qtdR}}}(P_n)\le n+1$.

Furthermore, if $n\equiv 0\hspace{1em}(\mathrm{\text{mod}}3)$, then since the unique ${\gamma }_{\mathit{\text{dR}}}(P_n)$-function is not a QTDRD-function of P_n we have ${\gamma }_{\mathit{\text{qtdR}}}(P_n)\ge n+1.$ For the remaining situations, it follows from Inequality (1) and Proposition 1 that ${\gamma }_{\mathit{\text{qtdR}}}(P_n)\ge n+1$. Therefore in either case ${\gamma }_{\mathit{\text{qtdR}}}(P_n)=n+1$. □

Theorem 4.

For $n\ge 3$, $${\gamma }_{\mathit{\text{qtdR}}}(C_n)=\{\begin{array}{cc}n\hfill & \mathit{\text{if}}n\equiv 0\hspace{1em}\left(\mathrm{\text{mod}}2\right)\hfill \\ n+1\hfill & \mathit{\text{if}}n\equiv 1\hspace{1em}\left(\mathrm{\text{mod}}2\right).\hfill \end{array}$$

Proof.

Let $C_n=v_1{v}_2\dots v_n{v}_1$ be a cycle on n vertices. Define the function f on $V(C_n)$ by $f(v_{2i-1})=2$ for each $1\le i\le \lceil \frac{n}{2}\rceil$ and f(x) = 0, otherwise. It is easy to see that f is a QTDRD-function of C_n of weight $2\lceil \frac{n}{2}\rceil$ and thus ${\gamma }_{\mathit{\text{qtdR}}}(C_n)\le n$ when n is even and ${\gamma }_{\mathit{\text{qtdR}}}(C_n)\le n+1$ when n is odd.

Furthermore, if n is even, then it follows from Inequality (1) and Proposition 2 that ${\gamma }_{\mathit{\text{qtdR}}}(C_n)=n$. If $n\equiv 1,5\hspace{1em}(\mathrm{\text{mod}}6)$, then Inequality (1) and Proposition 2 implies that ${\gamma }_{\mathit{\text{qtdR}}}(C_n)\ge n+1$ and so ${\gamma }_{\mathit{\text{qtdR}}}(C_n)=n+1$. Finally, assume that $n\equiv 3\hspace{1em}(\mathrm{\text{mod}}6)$. Clearly, none of the functions f_j is a QTDRD-function of C_n implying that ${\gamma }_{\mathit{\text{qtdR}}}(C_n)\ge n+1$, and thus ${\gamma }_{\mathit{\text{qtdR}}}(C_n)=n+1$. □

2 NP-completeness result

In this section, we will show that the decision problem defined below for the quasi total double Roman domination number is NP-complete even for bipartite graphs.

Quasi total double Roman domination problem (QTDRDP):

Instance: A nonempty bipartite graph G and a positive integer k.

Question: Does G have a QTDRD-function of weight at most k?

Following Garey and Johnson’s techniques for proving NP-completeness given in [15], we prove our result by describing a polynomial transformation from the well-known NP-complete problem 3SAT. Before stating problem 3SAT, we 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 while 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 literal $\overline{u}$ is false under t, and of course the literal $\overline{u}$ is true if and only if the literal 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 3SAT is specified as follows.

3-satisfiability problem (3SAT):

Instance: A collection $\mathcal{C}=\{C_1,C_2,\dots ,C_m\}$ of clauses over a finite set U of variables such that $\left|C_j\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 5.

[15, Theorem 3.1] 3SAT problem is NP-complete.

Now, we are ready to show the NP-completeness of the QTDRD problem for bipartite graphs.

Theorem 6.

The QTDRD problem is NP-complete for bipartite graphs.

Proof.

QTDRD is a member of NP, because we can verify in polynomial time that a function $f:V\to \{0,1,2,3\}$ is a QTDRD-function and has weight at most k. Let us now show that how to transform any instance of 3SAT into an instance G of QTDRD such that one of them has a solution if and only if the other one has a solution.

The transformation is from 3SAT. Suppose that $U=\{u_1,u_2,\dots ,u_n\}$ and let $\mathcal{C}=\{C_1,C_2,\dots ,C_m\}$ be an arbitrary instance of 3SAT. We construct a bipartite graph G and chose a positive integer k such that ${\gamma }_{\mathit{\text{qtdR}}}(G)\le k$ if and only if $\mathcal{C}$ is satisfiable. The construction of G is as follows.

For each variable $u_i\in U$, we associate a complete bipartite graph $H_i=K_{4,4}$ with bipartite sets $X_i=\{x_i,y_i,z_i,w_i\}$ and $Y_i=\{u_i,t_i,\overline{u_i},v_i\}$. For each clause $C_j=\{p_j,q_j,r_j\}\in \mathcal{C}$, we associate a single vertex c_j and we add the edge set $c_j{u}_i$ if $u_i\in C_j$ and $c_j\overline{u_i}$ if $\overline{u_i}\in C_j$. Clearly, G is a bipartite graph of order $8n+m$, and of course the construction can be accomplished in polynomial time (Figure 1). All that remains to be shown is that $\mathcal{C}$ is satisfiable if and only if ${\gamma }_{\mathit{\text{qtdR}}}(G)=6n$. This aim can be fulfilled by proving the following claims.

Fig. 1 An instance of the quasi total double Roman number problem resulting from an instance of 3SAT. Here k = 1 and ${\gamma }_{\mathit{\text{qtdR}}}(G)=24$, where the bold vertex p means there is a QTDRD-function f with f(p) = 3.

Claim 1. ${\gamma }_{\mathit{\text{qtdR}}}(G)\ge 6n$. Moreover, if ${\gamma }_{\mathit{\text{qtdR}}}(G)=6n$, then for any γ_qtdR-function $f=(V_0,V_1,V_2,V_3)$ on G, $f(V(H_i))=6$ and $\left|\right\{u_i,\overline{u_i}\}\cap V_3|\le 1,\{u_i,\overline{u_i}\}\cap (V_1\cup V_2)=\varnothing$ for each $i\in \{1,2,\dots ,n\}$, while $f(c_j)=0$ for each $j\in \{1,2,\dots ,m\}$.

Proof of Claim 1. Let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{\mathit{\text{qtdR}}}(G)$-function. By the construction of G, we have $f(V(H_i))\ge 6$ for each i, and therefore ${\gamma }_{\mathit{\text{qtdR}}}(G)\ge 6n$.

Suppose now that ${\gamma }_{\mathit{\text{qtdR}}}(G)=6n$. Then $f(V(H_i))=6$ for each $i\in \{1,2,\dots ,n\}$ and so ${\sum }_{j=1}^{m}f(c_j)=0$. Also, it is clear that $\left|\right\{u_i,\overline{u_i}\}\cap V_3|\le 1$ for each $i\in \{1,2,\dots ,n\}$. Now if $f(u_i)=f(\overline{u_i})=1$ or $f(u_i)=1$ and $f(\overline{u_i})=2$ ($f(u_i)=2$ and $f(\overline{u_i})=1$ is similar), then $f(X_i)+f(t_i)+f(v_i)\ge 5$, this implies that $f(H_i)\ge 7$, a contradiction. Moreover, if $f(u_i)=f(\overline{u_i})=2$, then $f(X)+f(t_i)+f(v_i)\ge 3$ and so $f(H_i)\ge 7$, a contradiction again. Therefore $\{u_i,\overline{u_i}\}\cap (V_1\cup V_2)=\varnothing$ for each $i\in \{1,2,\dots ,n\}$, and the proof of the claim is complete. ◆

Claim 2. ${\gamma }_{\mathit{\text{qtdR}}}(G)=6n$ if and only if $\mathcal{C}$ is satisfiable.

Proof of Claim 2. Suppose that ${\gamma }_{\mathit{\text{qtdR}}}(G)=6n$ and let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{\mathit{\text{qtdR}}}(G)$-function. By Claim 1, $f(V(H_i))=6,\left|\right\{u_i,\overline{u_i}\}\cap V_3|\le 1,\{u_i,\overline{u_i}\}\cap (V_1\cup V_2)=\varnothing$ for each $i\in \{1,2,\dots ,n\}$ and ${\sum }_{j=1}^{m}f(c_j)=0$. Define a mapping $t:U\to \{T,F\}$ by (2) $$t(u_i)=\{\begin{array}{cc}T\hfill & \text{if}f(u_i)=3\hfill \\ F\hfill & \text{otherwise}.\hfill \end{array}$$(2)

Arbitrarily choose a clause $C_j\in \mathcal{C}$. Then there exits some $i\in \{1,2,\dots ,n\}$ such that c_j is adjacent to either $u_i\in V_3$ or to $\overline{u_i}\in V_3$. Suppose, without loss of generality, that $c_j\overline{u_i}\in E(G)$ and $\overline{u_i}\in V_3$. Since $\{u_i,\overline{u_i}\}\cap (V_1\cup V_2)=\varnothing$ and $\left|\right\{u_i,\overline{u_i}\}\cap V_3|\le 1$, we have $t(\overline{u_i})=T$ by (2), implying that the clause C_j is satisfied by t. Because of the arbitrariness of j with $1\le j\le m,\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}$. First, construct a subset D of vertices of G as follows. If $t(u_i)=T$, then put the vertices u_i and x_i into D; if $t(u_i)=F$, then put the vertices $\overline{u_i}$ and x_i into D. Then define the function g on V(G) by g(x) = 3 for every $x\in D$ and g(y) = 0 for any $y\in V(G)-D.$ Since t is a satisfying truth assignment for $\mathcal{C}$, the corresponding vertex c_j in G is adjacent to at least one vertex in D. It can be checked that g is a QTDRD-function of G of weight 6n and so ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 6n$. The equality follows from Claim 1, that is, ${\gamma }_{\mathit{\text{qtdR}}}(G)=6n$. ◆

This completes the proof. □

3 Graphs G with small or large ${\gamma }_{\mathit{\text{qtdR}}}(G)$

In this section, we provide a characterization of all graphs with small or large quasi total double Roman domination number. Obviously, for every nontrivial connected graph G, ${\gamma }_{\mathit{\text{qtdR}}}(G)\ge 3.$ Therefore, we start by characterizing connected graphs G for which ${\gamma }_{\mathit{\text{qtdR}}}(G)\in \{3,4,5\}.$ Let us recall that the join $G\vee H$ of two graphs G and H is a graph formed from disjoint copies of G and H by connecting each vertex of G to each vertex of H. Also G – e denotes the graph resulting from G by removing an edge e.

Proposition 7.

Let G be a connected graph of order $n\ge 2$. Then

1. ${\gamma }_{\mathit{\text{qtdR}}}(G)=3$ if and only if $G\cong P_2.$

2. ${\gamma }_{\mathit{\text{qtdR}}}(G)=4$ if and only if $\Delta (G)=n-1$ or $G\cong \overline{K_2}\vee H$, where H is any graph.

3. ${\gamma }_{\mathit{\text{qtdR}}}(G)=5$ if and only if G is a graph obtained from $\overline{K_2}\vee H$, by removing exactly one edge between $\overline{K_2}$ and H, where H is a graph with $\Delta (H)\le |V(H)|-2$.

Proof.

Let $f=(V_0,V_1,V_2,V_3)$ be a ${\gamma }_{\mathit{\text{qtdR}}}$-function on G, and note that ${\gamma }_{\mathit{\text{qtdR}}}(G)=3\left|V_3\right|+2\left|V_2\right|+\left|V_1\right|$.

(i) Assume that ${\gamma }_{\mathit{\text{qtdR}}}(G)=3$. Then $3\left|V_3\right|+2\left|V_2\right|+\left|V_1\right|=3$ and by the definition of a QTDRD-function on G, we must have $V_3=\varnothing$ and $\left|V_2\right|=\left|V_1\right|=1.$ Hence $V_0=\varnothing$ and thus $G=P_2$. For the converse, clearly if $G=P_2$, then ${\gamma }_{\mathit{\text{qtdR}}}(G)=3$.

(ii) Assume now that ${\gamma }_{\mathit{\text{qtdR}}}(G)=4$. Then one of the following situations holds:

1. $\left|V_1\right|=\left|V_3\right|=1$ and $\left|V_2\right|=0$;

2. $\left|V_1\right|=2,\left|V_2\right|=1$ and $\left|V_3\right|=0$;

3. $\left|V_2\right|=2$ and $\left|V_1\right|=\left|V_3\right|=0$.

If (1) holds, let $V_3=\left\{v\right\}.$ Then each vertex of $V(G)\setminus \left\{v\right\}$ must be adjacent to v and thus $\Delta (G)=n-1$. If (2) holds, then $V_0=\varnothing$ and so $n=\left|V_1\right|+\left|V_2\right|=3$, implying again that $\Delta (G)=n-1$. Finally, assume that (3) holds and let $V_2=\{u,v\}$. Then each vertex in $V(G)\setminus \{u,v\}$ is adjacent to both vertices v and u. If $\mathit{\text{uv}}\in E(G)$, then $\Delta (G)=n-1$, while if $\mathit{\text{uv}}\notin E(G)$, then clearly $G\cong \overline{K_2}\vee H,$ where $H=G[V(G)\setminus \{u,v\}]$.

Conversely, if $\Delta (G)=n-1$, then ${\gamma }_{\mathit{\text{qtdR}}}(G)=4$. If $G=\overline{K_2}\vee H,$ then to avoid the previous case, we can assume that $\Delta (H)\le |V(H)|-2$. By item (i), ${\gamma }_{\mathit{\text{qtdR}}}(G)\ge 4$. The equality follows by assigning 2 to the vertices of $\overline{K_2}$ and 0 to those of H.

(iii) Assume that $G\cong (\overline{K_2}\vee H)-e$, where $\Delta (H)\le |V(H)|-2$ and e is an edge with an endvertex belonging to $\overline{K_2}$ and the other endvertex belongs to $V(H).$ Let $V(\overline{K_2})=\{u,v\},$ and $w\in V(H)$ such that $e=\mathit{\text{uw}}.$ By items (i) and (ii) ${\gamma }_{\mathit{\text{qtdR}}}(G)\ge 5$. To get the equality, consider the function g on V(G) defined by $g(u)=g(v)=2,$ g(w) = 1 and g(x) = 0 for $x\in V(G)\setminus \{u,v,w\}$. Clearly, g is a QTDRD-function of G with weight 5 and hence ${\gamma }_{\mathit{\text{qtdR}}}(G)=5$.

Conversely, let ${\gamma }_{\mathit{\text{qtdR}}}(G)=5$. Using the fact that $\left|V_1\right|+2\left|V_2\right|+3\left|V_3\right|=5,$ it can be seen that the only case to be considered is $\left|V_1\right|=1$ and $\left|V_2\right|=2$, and the other cases will be excluded because they lead us to have ${\gamma }_{\mathit{\text{qtdR}}}(G)=4$. Let $V_2=\{u,v\}$ and $V_1=\left\{w\right\}$. By definition u and v are adjacent to all vertices in $V(G)\setminus \{u,v,w\}$ and w is adjacent to one of vertices u and v, say u. Since ${\gamma }_{\mathit{\text{qtdR}}}(G+\mathit{\text{wv}})=4$, by item (ii), $G=\overline{K_2}\vee H,$ where $\Delta (H)\le |V(H)|-2$. Consequently, $G=(\overline{K_2}\vee H)-\mathit{\text{wv}}$ and the proof is complete. □

The next results are immediate consequences of Proposition 7.

Corollary 8.

For any graph of order $n\ge 3,{\gamma }_{\mathit{\text{qtdR}}}(G)\ge 4$.

Corollary 9.

Let $G=K_{n_1,n_2,\dots ,n_r}$ be the complete r-partite graph with $r\ge 2$ and $1\le n_1\le n_2\le \cdots \le n_r$ of order $n=n_1+n_2+\cdots +n_r\ge 3$.

1. If $1\le n_1\le 2$, then ${\gamma }_{\mathit{\text{qtdR}}}(G)=4$;

2. If $n_1\ge 3$, then ${\gamma }_{\mathit{\text{qtdR}}}(G)=6$.

In the aim of characterizing graphs with large quasi total double Roman domination number, we need to state the next two upper bounds.

Proposition 10.

For any graph G of order n, $${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-2\Delta (G)+2.$$

This bound is sharp for stars and $F_{r,t}$ with $r\ge 2$ and $t\ge 0$.

Proof.

Let v be a vertex with maximum degree $\Delta (G)$ and let w be a neighbor of v. It can be seen that $(N(v)-\{w\},\{w\},V(G)-N[v],\{v\})$ is a QTDRD-function of G with weight $2n-2\Delta (G)+2$. Thus ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-2\Delta (G)+2$. □

The upper bound in Proposition 10 will be slightly improved for regular and semi-regular graphs.

Proposition 11.

If G is a connected k-regular graph of order $n\ge 3$ with $k<n-1$, then ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-2k$.

Proof.

Let v be a vertex of G. Assume that $N(v)=\{v_1,v_2,\dots ,v_k\}$ and let $X=V(G)-N[v]$. Since $k<n-1$, we have $X\ne \varnothing$. If each v_i has a neighbor in X, then the function g given by g(x) = 2 for $x\in X\cup \left\{v\right\}$ and g(x) = 0 otherwise, is a QTDRD-function of G of weight $2n-2k$, as desired. Hence assume that $N(v_i)\cap X=\varnothing$ for some i, say i = k. Since G is regular, we deduce that each component of $G[X]$ has order at least two. Now, if $\Delta (G[X])\ge 2$ and $u\in X$ has maximum degree $\Delta (G[X])$ in $G[X]$, then the function g defined by g(v) = 3, $g(v_1)=1$, g(x) = 2 for $x\in X-\left\{u\right\}$ and g(x) = 0 otherwise, is a QTDRD-function of G of weight $2n-2k$, as desired. Hence we assume that $\Delta (G[X])=1$, and thus each component of $G[X]$ is isomorphic to K₂. Since v_k has no neighbor in X, each vertex in X is adjacent to all vertices in N(v) but v_k. Let $x_i{y}_i(1\le i\le t)$ be the vertices of a K₂-component of $G[X]$. Then the function g defined by g(v) = 2, $g(v_k)=1$, $g(x_i)=2,g(y_i)=1$ for $i\in \{1,\dots ,t\}$ and g(x) = 0 otherwise, is a QTDRD-function of G of weight at most $2n-2k$, as desired. This completes the proof. □

Proposition 12.

If G is a connected graph of order $n\ge 3$ with $\Delta (G)=\delta (G)+1<n-1$, then $${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-2\Delta (G)+1.$$

Proof.

Let v be a vertex of G with maximum degree $\Delta (G),N(v)=\{v_1,v_2,\dots ,v_{\Delta (G)}\}$ and $X=V(G)-N[v]$. Since $\Delta (G)<n-1$, we have $X\ne \varnothing$. If each v_i has a neighbor in X, then as in the proof of Proposition 11 we have ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-2\Delta (G)$. Hence we assume, without loss of generality, that $N(v_i)\cap X=\varnothing$ for some i, say $i=\Delta (G)$. If $\Delta (G[X])\ge 2$, then the same argument used in the proof of Proposition 11 leads to ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-2\Delta (G)$. Hence we assume that $\Delta (G[X])\le 1$. Note that any isolated vertex in $G[X]$ is of degree $\delta (G)$ since as assumed $v_{\Delta (G)}$ has no neighbor in X. Now if $G[X]$ has two isolated vertices u and $u^{\prime }$, then u and $u^{\prime }$ must be adjacent to all vertices in $N(v)-\left\{v_{\Delta (G)}\right\}$ and thus the function g defined by $g(v)=g(v_1)=3$, g(x) = 2 for $x\in X-\{u,u^{\prime }\}$ and g(x) = 0 otherwise, is a QTDRD-function of G of weight at most $2n-2\Delta (G)$, as desired. Henceforth, we assume that $G[X]$ has at most one isolated vertex. If $\left|X\right|=1$, then clearly $\Delta (G)=n-2$ and assigning a 2 to v and the unique vertex of X, a 1 to $v_{\Delta }$ and a 0 to the remaining vertices provides a QTDRD-function of weight $5=2n-2\Delta (G)+1$. Therefore, we can assume that $\left|X\right|\ge 2$, and thus $G[X]$ has a K₂-component, say $u{u}^{\prime }$. Then the function g given by $g(v)=3,g(v_1)=g(u)=1$, g(x) = 2 for $x\in X-\left\{u\right\}$ and g(x) = 0 otherwise, is a QTDRD-function of G of weight at most $2n-2\Delta (G)+1$ and the proof is complete. □

If G is a connected graph with $\Delta (G)=1$, then $G=K_2$ and ${\gamma }_{\mathit{\text{qtdR}}}(K_2)=3<2n-2\Delta (G)+2$. Hence the next results are immediate consequences of Proposition 10.

Corollary 13.

For any connected graph G of order $n\ge 3,{\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-2,$ with equality if and only if $G\in \{P_3,C_3\}$

Proof.

Since G is connected and $n\ge 3$, we have $\Delta (G)\ge 2$. If $\Delta (G)\ge 3$, then Proposition 10 leads to ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-4.$ Hence let $\Delta (G)=2$. Then G is a path P_n or a cycle C_n. If $G=P_n$, then by Theorem 3 we have ${\gamma }_{\mathit{\text{qtdR}}}(G)\le n+1\le 2n-2$ with equality if n = 3, that is $G=P_3$. If $G=C_n$, then by Theorem 4 we have ${\gamma }_{\mathit{\text{qtdR}}}(G)\le n+1\le 2n-2$ with equality if n = 3, that is $G=C_3$. □

Using a similar argument as above we get the following.

Corollary 14.

The path P₄ is the only connected graph G of order $n\ge 4$ satisfying ${\gamma }_{\mathit{\text{qtdR}}}(G)=2n-3.$

Proposition 15.

Let G be a connected graph of order $n\ge 4$ such that $G\ne P_4.$ Then ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-4,$ with equality if and only if $G\in \{P_5,C_4,C_5,F_{2,1},G_1,G_2,G_3,K_{1,3},K_4,K_4-e\}$, where G₁, G₂ and G – 3 are the graphs depicted in Figure 2.

Fig. 2 Some graphs G with ${\gamma }_{\mathit{\text{qtdR}}}(G)=2n-4$.

Proof.

If $\Delta (G)\ge 4$, then Proposition 10 leads to ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-6<2n-4.$ Hence $\Delta (G)\in \{2,3\}$. If $\Delta (G)=2$, then $G\in \{P_n,C_n\},$ and by Theorem 3, ${\gamma }_{\mathit{\text{qtdR}}}(P_n)\le 2n-4$ with equality if and only if n = 5, that is $G=P_5$, while by Theorem 4, ${\gamma }_{\mathit{\text{qtdR}}}(C_n)\le 2n-4$ with equality if and only if $n\in \{4,5\}$, that is $G\in \{C_4,C_5\}$. Hence, in the sequel we can assume that $\Delta (G)=3$. By Proposition 10, ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-4$, and the bound follows.

Assume now that ${\gamma }_{\mathit{\text{qtdR}}}(G)=2n-4.$ Let v be a vertex with degree 3 and let $N(v)=\{v_1,v_2,v_3\}$ and $X=V(G)-N[v]$. If there is an edge $\mathit{\text{xy}}\in G[X]$, then the function f defined on V(G) by f(v) = 3, $f(v_1)=1$, $f(v_2)=f(v_3)=0$, f(x) = 1 and f(z) = 2 otherwise, is a QTDRD-function of G of weight $2n-5$, a contradiction. Hence no two vertices in X are adjacent. If v₁ has at least two neighbors in X, then the function f defined on V(G) by $f(v)=f(v_1)=3,f(v_2)=f(v_3)=0$, f(x) = 0 for $x\in N(v_1)-N[v]$ and f(z) = 2 otherwise, is a QTDRD-function of G of weight $2n-6$ yielding a contradiction. Hence v₁ has at most one neighbor in X, and likewise for v₂ and $v_3.$ Moreover, since G is connected, each vertex in X must have a neighbor in N(v) implying that $\left|X\right|\le 3$. If $\left|X\right|=3$, say $=\{u_1,u_2,u_3\}$, then, without loss of generality, let $u_i{v}_i\in E(G)$ for every $i\in \{1,2,3\}.$ In this case, G has order 7 and the function g defined by $g(v)=g(u_1)=g(u_2)=g(u_3)=2$, and $g(v_1)=g(v_2)=g(v_3)=0$ is a QTDRD-function of G of weight $8=2n-6$ leading to a contradiction. If $\left|X\right|=2$, say $X=\{u_1,u_2\}$, then we may assume that $u_1{v}_1,u_2{v}_2\in E(G)$ and the function g defined by $g(v)=g(u_1)=g(u_2)=2,g(v_3)=1$ and $g(v_1)=g(v_2)=0$ is a QTDRD-function of G of weight $7=2n-5,$a contradiction too. Hence $\left|X\right|\le 1$. Now if $X=\varnothing$, then it follows from Corollary 14 that $G\in \{G_1,K_{1,3},K_4,K_4-e\}$. Finally, assume that $\left|X\right|=1$ and let $X=\left\{u\right\}$. Since G is connected, let $u{v}_1\in E(G)$. If $u{v}_2\in E(G)$, then the function g defined by $g(v)=g(u)=2$, $g(v_3)=1$ and $g(v_1)=g(v_2)=0$, is a QTDRD-function of G of weight $5=2n-5,$a contradiction. Thus $u{v}_2\notin E(G)$ and similarly $u{v}_3\notin E(G),$ implying that u is a leaf. If $\mathrm{\text{deg}}(v_2)=3$, then the function g defined by $g(v_1)=g(v_3)=2$, g(u) = 1 and $g(v)=g(v_2)=0$, is a QTDRD-function of G of weight $5=2n-5,$a contradiction. Hence $\mathrm{\text{deg}}(v_2)\le 2$ and likewise $\mathrm{\text{deg}}(v_3)\le 2$. It follows that $G\in \{F_{2,1},G_2,G_3\}$.

If $G\in \{P_5,C_4,C_5,F_{2,1},G_1,G_2,G_3,K_{1,3},K_4,K_4-e\}$, then it is easy to see that ${\gamma }_{\mathit{\text{qtdR}}}(G)=2n-4.$ and the proof is complete. □

Proposition 16.

Let G be a connected graph G of order $n\ge 5$ such that $G\notin \{P_5,C_5,F_{2,1},G_2,G_3\}$. Then ${\gamma }_{\mathit{\text{qtdR}}}(G)\le 2n-5,$ with equality if and only if $G\in \{P_6,F_{1,2},\mathit{\text{cor}}(C_3),G_i|4\le i\le 10\}$, where $G_i(i=4,\dots ,10)$ are the graphs depicted in Figure 3.

Fig. 3 Some graphs G with ${\gamma }_{\mathit{\text{qtdR}}}(G)=2n-5$.

Proof.

The bound follows from Corollaries 13, 14, and Proposition 15. Assume now that ${\gamma }_{\mathit{\text{qtdR}}}(G)=2n-5$. As in the proof of Proposition 15, we may assume that $2\le \Delta (G)\le 3$. If $\Delta (G)=2$, then $G\in \{P_n,C_n\}$, and one can easily check by Theorem 3 that $G=P_6$ and by Theorem 4 no cycle satisfies ${\gamma }_{\mathit{\text{qtdR}}}(C_n)=2n-5.$ In the sequel, we can assume that $\Delta (G)=3$. Consider a vertex v of degree 3 and let $N(v)=\{v_1,v_2,v_3\}$ and $X=V(G)-N[v]$. If v₁ has two neighbors in X, then the function f defined on V(G) by f(v) = 3, $f(v_1)=3$, $f(v_2)=f(v_3)=0$, f(x) = 0 for $x\in N(v_1)\cap X$ and f(z) = 2 otherwise, is a QTDRD-function of G of weight $2n-6,$a contradiction. Hence each v_i has at most one neighbor in X. If there are two edges in $G[X]$ sharing a same endvertex, say xy, xz, then the function f defined on V(G) by f(v) = 3, $f(v_1)=1,f(v_2)=f(v_3)=0,f(z)=f(y)=2$, f(x) = 0 and f(a) = 2 otherwise, is a QTDRD-function of G of weight $2n-6,$a contradiction. Hence we assume that $\Delta (G[X])\le 1$. If $G[X]$ has two disjoint K₂-components, say $u_1{u}_2$ and $w_1{w}_2$, then the function f defined on V(G) by f(v) = 3, $f(v_1)=1,f(v_2)=f(v_3)=0,f(u_1)=f(w_1)=2,f(u_2)=f(w_2)=1$ and f(a) = 2 otherwise, is a QTDRD-function of G of weight $2n-6,$a contradiction too. Therefore, $G[X]$ has at most one K₂-component. Consider the following two cases.

Case 1. $G[X]$ has a K₂-component, say $u_{1}w$.

Since G is connected and each v_i has at most one neighbor in X, we deduce that $\left|X\right|\le 4$. Assume first that $X=\{u_1,w,u_2,u_3\}$, and without loss of generality, let $u_i{v}_i\in E(G)$ for each i. Then the function g defined by $g(v)=g(u_i)=2$ for $i\in \{1,2,3\}$, g(w) = 1 and $g(v_i)=0$ for every $i\in \{1,2,3\}$, is a QTDRD-function of G of weight $2n-7,$a contradiction. Assume now that $X=\{u_1,w,u_2\}$, where without loss of generality, $u_i{v}_i\in E(G)$ for $i=1,2.$ Then the function g defined by $g(v)=g(u_i)=2$ for i = 1, 2, $g(w)=g(v_3)=1$ and $g(v_i)=0$ for i = 1, 2, is a QTDRD-function of G of weight $2n-6,$a contradiction. Therefore $\left|X\right|=2,$ that is $X=\{u_1,w\}$, where $v_1{u}_1\in E(G).$ If u₁ is adjacent to v₂ or v₃, say v₂, then assigning 2 to $v,u_1$, 1 to $v_3,w$ and 0 to v₁ and v₂ provides a QTDRD-function of G of weight 6 which leads to a contradiction. Hence $\mathrm{\text{deg}}(u_1)=2$. If w is adjacent to v₂ and $v_3,$ then assigning a 2 to $v,v_1$ and w, a 0 to v₂, v₃ and u₁ provides a QTDRD-function of weight $6<2n-5,$a contradiction. Hence w is adjacent to at most one of v₂ and $v_3.$ Recall that each vertex of N(v) is adjacent to at most one vertex of X, and hence $v_{1}w\notin E(G).$ Now because of its degree, v₁ is adjacent to at most one of v₂ and $v_3.$ If $w{v}_2\in E(G),$ then $v_1{v}_2\notin E(G)$ for otherwise assigning a 2 to $v_1,v_3,w$ and a 0 to $v,v_2$ and u₁ provides a QTDRD-function of weight $6<2n-5,$a contradiction. Similarly it can be seen that $v_1{v}_3\notin E(G)$ and thus $G\cong G_9$. In the next, we assume that $w{v}_2,w{v}_3\notin E(G),$ that is w is a leaf. In this case, it is not hard to see that $G\in \{G_7,G_8,G_{10}\}$.

Case 2. $G[X]$ has no K₂-component.

Since G is connected and each v_i has at most one neighbor in X, $\left|X\right|\le 3$. As in the proof of Proposition 15, it can be seen that if $\left|X\right|=3,$ we can construct a QTDRD-function of G of weight $2n-6$. Hence $\left|X\right|\le 2$ and of course $\left|X\right|\ge 1$ (because of $n\ge 5$). If $X=\left\{u_1\right\}$, then let $u_1{v}_1\in E(G)$, and thus $G\in \{G_4,G_5,G_6\}$. Finally, let $X=\{u_1,u_2\}$ and assume that $u_i{v}_i\in E(G)$ for i = 1, 2. It is not hard to see that $G\in \{F_{1,2},\mathit{\text{Cor}}(C_3),G_7\}$. This completes the proof. □

4 An upper bound

In this section, we show that for any connected graph G with order $n\ge 3$, ${\gamma }_{\mathit{\text{qtdR}}}(G)\le \frac{5n}{4}$. Since deleting an edge cannot decrease the quasi total double Roman domination number, it is enough to prove the result for trees. We then characterize the connected graphs attaining the upper bound. We start with a simple observation and recalling a result from [3].

Observation 17.

If v is a strong support vertex of a graph G, then there exists a ${\gamma }_{\mathit{\text{qtdR}}}(G)$-function f that assigns 3 to v and 0 to every leaf neighbor of v.

Let $\mathcal{T}$ be a family of trees which obtained from k paths $P_4=u_i^1{u}_i^2{u}_i^3{u}_i^4(k\ge 1)$ by adding k – 1 edges between $u_i^2$s such that the resulting graphs is connected (see Figure 4 for k = 3). The proof of the following theorem can be found in [3].

Fig. 4 Graph T.

Theorem 18

([3]). For any tree T of order $n\ge 4,{\gamma }_{\mathit{\text{dR}}}(T)\le \frac{5}{4}n,$ with equality if and only if $T\in \mathcal{T}$.

Corollary 19.

If $T\in \mathcal{T}$ is a tree of order n, then ${\gamma }_{\mathit{\text{qtdR}}}(T)=\frac{5}{4}n$.

Proof.

Assume that $T\in \mathcal{T}$, and let us use the same labeling of vertices described for the construction of T. Note that $k=\frac{n}{4}.$ Then assigning a 2 to $u_i^2$ and $u_i^4$ for every i, a 1 to every $u_i^1$ and a 0 to the remaining vertices provides a QTDRD-function of T of weight $5k=5\frac{n}{4},$ leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5}{4}n.$ Moreover, by (1) and Theorem 18, we obtain $\frac{5n}{4}={\gamma }_{\mathit{\text{dR}}}(T)\le {\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5n}{4},$ and thus ${\gamma }_{\mathit{\text{qtdR}}}(T)=\frac{5}{4}n$. □

Theorem 20.

Let T be a tree of order $n\ge 4$. Then $${\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5}{4}n,$$with equality if and only if $T\in \mathcal{T}$.

Proof.

Let T be a tree of order $n\ge 4$. We will proceed by induction on the order n. If n = 4, then $T\in \{P_4,K_{1,3}\}$ and clearly ${\gamma }_{\mathit{\text{qtdR}}}(T)\le 5=\frac{5n}{4}$ with equality if and only if $T=P_4$ which belongs to $\mathcal{T}$. This establishes the base case. Let $n\ge 5$ and assume that if $T^{\prime }$ is a tree of order $n^{\prime }$, where $n^{\prime }<n$ and $n^{\prime }\ge 4$, then ${\gamma }_{\mathit{\text{qtdR}}}(T\prime )\le \frac{5n^{\prime }}{4}$ with equality if and only if $T^{\prime }\in \mathcal{T}$. If T is a star, then the function that assigns 3 to the central vertex, 1 to one of leaves and 0 to other leaves of the star, is a QTDRD-function of T of weight 4, and so ${\gamma }_{\mathit{\text{qtdR}}}(T)=4<\frac{5n}{4}$. Hence, we may assume that T is not a star and thus $\text{diam} (T)\ge 3$. If $\text{diam} (T)=3$, then T is a double star $T\cong D{S}_{r,s}$, where $r\ge s\ge 1$ and $r\ge 2$. Let u and v be the two support vertices of T, where u has r leaf neighbors and v has s leaf neighbors. Then the function that assigns 3 to u and v and 0 to any leaf of T is a QTDRD-function of T of weight 6, leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)=6<\frac{5n}{4}$. Hence, we can assume that $\text{diam} (T)\ge 4$, for otherwise the desired result follows.

If T has a support vertex x with at least three leaf neighbors, then consider the tree $T^{\prime }$ obtained from T by removing one leaf neighbor of x, say y. Observe that x remains a strong support vertex in $T^{\prime }$. By Observation 17, x is assigned 3 under some γ_qtdR-function f on $T^{\prime },$ and such a ${\gamma }_{\mathit{\text{qtdR}}}$-function can be extended to a QTDRD-function of T by assigning a 0 to y, leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le {\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })\le \frac{5n^{\prime }}{4}=\frac{5(n-1)}{4}<\frac{5n}{4}$. Therefore, we can assume that every support vertex in T is adjacent to one or two leaves.

Let $v_1{v}_2\dots v_k$ be a diametral path of T chosen such that ${\mathrm{\text{deg}}}_T(v_2)$ is as large as possible. Note that v₂ is a support vertex and thus ${\mathrm{\text{deg}}}_T(v_2)\in \{2,3\}.$ Root T at v_k, and consider the following cases.

Case 1. ${\mathrm{\text{deg}}}_T(v_2)=3$.

Thus v₂ has exactly two leaf neighbors. Let $T^{\prime }=T-T_{v_2}$, and note that $T^{\prime }$ has order $n^{\prime }\ge 3,$ since $\text{diam} (T)\ge 4$. If $n^{\prime }=3,$ then T is a tree obtained from the path $v_1{v}_2{v}_3{v}_4{v}_5$ by adding a vertex u and an edge $v_{2}u$. In this case, assigning 3 to v₂ and v₄, 1 to v₃ and 0 to every leaf of T provides a QTDRD-function of T with weight 7, and thus ${\gamma }_{\mathit{\text{qtdR}}}(T)=7<\frac{5n}{4}$. Hence, we may assume that $n^{\prime }\ge 4$. Applying the induction hypothesis on $T^{\prime }$, we have ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })\le \frac{5(n-3)}{4}$. Now, if there exists a γ_qtdR-function $f^{\prime }$ of $T^{\prime }$ such that $f^{\prime }(v_3)\ne 0$, then $f^{\prime }$ can be extended to a QTDRD-function of T by assigning 3 to v₂ and 0 to its two leaf neighbors, yielding ${\gamma }_{\mathit{\text{qtdR}}}(T)\le {\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+3\le \frac{5(n-3)}{4}+3<\frac{5n}{4}$. Henceforth, we may assume that every ${\gamma }_{\mathit{\text{qtdR}}}$-function of $T^{\prime }$ assigns 0 to v₃. According the choice of v₂ on the diametral path, let s be the number of children of v₃, with degree 3, other than v₂, r be the number of children of v₃ with degree 2 and t be the number of leaf neighbors of v₃ in T. Observe that if $t\ge 2$ (resp. $r\ge 2$), then v₃ would be assigned a 3 (resp. 2) under some γ_qtdR-function of $T^{\prime }$, contradicting our earlier assumption. Hence $t\le 1$ and $r\le 1$. Similarly, if $s\ge 1$, then v₃ could be assigned at least 1 under some γ_qtdR-function of $T^{\prime }$, contradicting our earlier assumption again. Hence s = 0.

Assume first that $t=1.$ Let $v^{\prime }$ denote the leaf neighbor of v₃, and let $f^{\prime }$ be a γ_qtdR-function of $T^{\prime }$. By our earlier assumption we have $f^{\prime }(v_3)=0$ and thus $f(v^{\prime })=2$. If r = 1, then $f^{\prime }(V(T_{v_3}^{\prime }))=5$. In this case, form f from ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function $f^{\prime }$, by letting $f(x)=f^{\prime }(x)$ for all $x\in T-T_{v_3},f(v_2)=f(v_3)=3,f(z)=2$ for the leaf neighbor of the child of v₃ with degree 2 and f(z) = 0 for the remaining vertices of $T_{v_3}.$ Then f is a QTDRD-function of T, leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le f^{\prime }(T-T_{v_3})+8={\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+3\le \frac{5(n-3)}{4}+3<\frac{5n}{4}$. If r = 0, then let $T^{\prime }=T-T_{v_3}$. Since $\text{diam} (T)\ge 4$, $T^{\prime }$ has order $n^{\prime }\ge 2$. If $n^{\prime }=2$, then T is isomorphic to the tree T₁ depicted in Figure 5 and it is easy to see that ${\gamma }_{\mathit{\text{qtdR}}}(T_1)=8<\frac{5n}{4}$, as desired. If $n^{\prime }=3$, then T is one of the two trees illustrated in Figure 6, and it is easy to see that ${\gamma }_{\mathit{\text{qtdR}}}(T_2)={\gamma }_{\mathit{\text{qtdR}}}(T_3)=9<10=\frac{5n}{4}$, as desired. Hence, we may assume that $n^{\prime }\ge 4$. Applying the induction hypothesis on $T^{\prime }$, we have ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })\le \frac{5n^{\prime }}{4}$. Since any ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function can be extended to a QTDRD-function of T by assigning 3 to the vertices v₂ and v₃, and 0 to each leaf at $T_{v_3},$ we get $$\begin{array}{c}{\gamma }_{\mathit{\text{qtdR}}}(T)\le {\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+6\le \frac{5n^{\prime }}{4}+6=\frac{5(n-5)}{4}+6\\ =\frac{5n}{4}-\frac{1}{4}<\frac{5n}{4}.\end{array}$$

Fig. 5 Tree T₁.

Fig. 6 Trees T₂ and T₃, respectively.

Now, assume that t = 0, and let $T^{\prime }$ be tree obtained from T by deleting v₃ and its descendants, that is $T^{\prime }=T-T_{v_3}$. Note that $r\in \{0,1\}.$ Since $\text{diam} (T)\ge 4,T^{\prime }$ has order $n^{\prime }\ge 2$. If $n^{\prime }=2$, then we have two possible trees, either T is obtained from two disjoint paths P₅ and P₃ by adding an edge between their centers or T is a obtained from a path P₅ by adding a new vertex attached to a support vertex of the path P₅. In either case, it can be seen that ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}.$ Now, if $n^{\prime }=3,$ then T is isomorphic to one of the trees illustrated in Figure 7 and it can be seen that each of these four trees T satisfies ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}.$ Consequently, we can assume in the next that $n^{\prime }\ge 4$. Applying the induction hypothesis on $T^{\prime }$, we have ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })\le \frac{5n^{\prime }}{4}$. Let $f^{\prime }$ be a ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function. If r = 0, then we extend $f^{\prime }$ to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+4$ by assigning 3 to v₂, 1 to v₃ and 0 to the two leaf neighbors of v₂. If r = 1, then we extend $f^{\prime }$ to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+7$ by assigning 3 to the two children of v₃, 1 to v₃ and 0 to all leaves of $T_{v_3}$. Each case leads to ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$.

Fig. 7 Four trees T with ${\gamma }_{\mathit{\text{qtdR}}}(T)<5n/4$.

Case 2. ${\mathrm{\text{deg}}}_T(v_2)=2$.

By the choice of the diametral path, each child of v₃ has degree at most two. Let r be the number of children of v₃ with degree 2 and t be the number of leaves adjacent to v₃. Note that $r\ge 1$ and $t\ge 0.$ Let $T^{\prime }$ be the tree obtained from T by deleting v₃ and all its descendants. Since $\text{diam} (T)\ge 4,T^{\prime }$ has order $n^{\prime }\ge 2$. If $n^{\prime }=2,$ then $T\cong F_{t,r+1}$ and so $${\gamma }_{\mathit{\text{qtdR}}}(T)=\{\begin{array}{cc}2(r+1)+2,\hfill & \text{if}t=0\hfill \\ 2(r+1)+3,\hfill & \text{if}t=1\hfill \\ 2(r+1)+4,\hfill & \text{if}t\ge 2.\hfill \end{array}$$

Since $n=2(r+1)+t+1$ and $r\ge 1$, we get ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$. If $n^{\prime }=3$, then T is a tree belonging to the two families of trees illustrated in Figure 8 and so $n=t+2r+4$. If $T\in {\mathcal{T}}_7$, then it can be seen that $${\gamma }_{\mathit{\text{qtdR}}}(T_7)=\{\begin{array}{cc}2r+5,\hfill & \text{if}t=0\hfill \\ 2r+6,\hfill & \text{if}t\ge 1,\hfill \end{array}$$

Fig. 8 Families ${\mathcal{T}}_7$ and ${\mathcal{T}}_8$.

while, if $T\in {\mathcal{T}}_8$, then $${\gamma }_{\mathit{\text{qtdR}}}(T_8)\le \{\begin{array}{cc}2r+5,\hfill & \text{if}t=0\hfill \\ 2r+7,\hfill & \text{if}t\ge 1\text{and max}\{t,r\}\ge 2\hfill \\ 8,\hfill & \text{if}t=r=1.\hfill \end{array}$$

In either case, we have ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$, as desired. Therefore, we may assume in the next that $n^{\prime }\ge 4$. Applying the induction hypothesis on $T^{\prime }$, we have ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })\le \frac{5n^{\prime }}{4}$. Now, if $t\ge 2$, then any ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function $f^{\prime }$, can be extended to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+4+2r$ by assigning 3 to v₃, 2 to every leaf neighbor of $T_{v_3}$ not adjacent to $v_3,$ 1 to one leaf neighbor of v₃ and 0 to the remaining vertices of $T_{v_3}$. It follows that $$\begin{array}{c}{\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5n^{\prime }}{4}+4+2r=\frac{5(n-(t+2r+1))}{4}+2r+4\\ =\frac{5n-2r-5t+3}{4}<\frac{5n}{4},\end{array}$$as desired. Assume now that t = 1. Then any ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function $f^{\prime }$ can be extended to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+3+2r$ by assigning 2 to v₃ and all leaves of $T_{v_3}$ that are not adjacent to $v_3,$ 1 to the unique leaf neighbor of v₃ and 0 to the remaining vertices of $T_{v_3}$. It follows that $$\begin{array}{c}{\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5n^{\prime }}{4}+3+2r=\frac{5(n-(2r+2))}{4}+2r+3\\ =\frac{5n-2r+2}{4}\le \frac{5n}{4},\end{array}$$ as desired.

Further if ${\gamma }_{\mathit{\text{qtdR}}}(T)=\frac{5n}{4},$ then we have equality throughout the previous inequality chain. In particular, we have r = 1 and ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })=\frac{5n^{\prime }}{4}$. Thus by the induction hypothesis on $T^{\prime },T^{\prime }\in \mathcal{T}$. Hence we can assume that $T^{\prime }$ obtained by from k paths $P_4^i=u_i^1{u}_i^2{u}_i^3{u}_i^4(k\ge 1)$ by adding k – 1 edges between $u_i^2$’s such that the resulting graph is connected. Without loss of generality, assume that $v_4\in V(P_4^1)$ and let w denote the unique leaf neighbor of $v_3.$ If $v_4=u_1^1$ (the case $v_4=u_1^4$ is similar), then the function f defined on V(T) by $f(u_i^1)=1,f(u_i^2)=f(u_i^4)=2$ for $i\in \{2,\dots ,k\},f(u_1^2)=f(u_1^4)=f(v_3)=f(v_1)=2$, f(w) = 1, and f(x) = 0 otherwise, is a QTDRD-function of T of weight less than $\frac{5n}{4},$a contradiction. If $v_4=u_3^1$, then the function f defined on V(T) by $f(u_i^2)=f(u_i^4)=2,f(u_i^1)=1$ for $i\in \{2,\dots ,k\},f(u_1^1)=f(u_1^4)=2,f(v_3)=f(v_1)=2$, f(w) = 1, and f(x) = 0 otherwise, is a QTDRD-function of T of weight less than $\frac{5n}{4},$a contradiction again. Therefore, $v_4=u_1^2$ and so $T\in \mathcal{T}$.

Now, let t = 0. If $\mathrm{\text{deg}}(v_3)\ge 3$, then form f from any ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$ by assigning 2 to v₃ and to each leaf at distance two from v₃ in $T_{v_3}$ and 0 to the children of v₃. Using the induction hypothesis on $T^{\prime },$ it follows that $$\begin{array}{c}{\gamma }_{\mathit{\text{qtdR}}}(T)\le {\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+2r+2\le \frac{5n^{\prime }}{4}+2r+2\\ \le \frac{5(n-(2r+1))}{4}+2r+2=\frac{5n-2r+3}{4}<\frac{5n}{4},\end{array}$$as desired. Hence we can assume in the sequel that ${\mathrm{\text{deg}}}_T(v_3)=2$.

First let ${\mathrm{\text{deg}}}_T(v_4)=2$ and consider tree $T^{\prime }$ obtained from T by removing the set of vertices $\{v_1,v_2,v_3,v_4\}$. If $n(T^{\prime })\in \{2,3\}$, then by the choice of the diametral path, we have $T\in \{P_6,P_7\}$ and clearly ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$. Hence assume that $n(T^{\prime })\ge 4$. By the induction hypothesis on $T^{\prime },$ ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })\le \frac{5n(T^{\prime })}{4}$. Now, if ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })<\frac{5n(T^{\prime })}{4}$, then noting that any ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function can be extended to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+5$ by assigning 2 to v₄, v₂, 1 to v₁ and 0 to v₃, we get ${\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5(n-4)-1}{4}+5<\frac{5n}{4}$. Thus suppose that ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })=\frac{5n(T^{\prime })}{4}$. By the induction hypothesis $T^{\prime }\in \mathcal{T}$, and thus $T^{\prime }$ obtained from k paths $P_4^i=u_i^1{u}_i^2{u}_i^3{u}_i^4(k\ge 1)$ by adding k – 1 edges between $u_i^2$’s so that the resulting graph is connected. Further, we may assume that $v_5\in V(P_4^1).$ Note that assigning 2 to $u_i^2$’s and $u_i^4$’s, 1 to every $u_i^1$ and 0 to all $u_i^3$’s provides a ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function, say g. Now, if $v_5\in \{u_1^2,u_1^4\}$, then g can be extended to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+4$ by assigning 2 to v₃, v₁ and 0 to v₄, v₂, leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5(n-4)}{4}+4<\frac{5n}{4}$. If $v_5\in \{v_1,v_3\}$, then we can reassign the values on $V(P_4^1)$ so that these two vertices receive 2 which leads to a contradiction as above.

Finally we can assume that $\mathrm{\text{deg}}(v_4)\ge 3$. Observe that if we consider the tree $T^{\prime }=T-T_{v_3}$ such that there is a ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function which assigns at least 2 to v₄, then such a function can be extended to QTDRD-function of T by assigning 2 to $v_2,$ 1 to v₁ and 0 to v₃ leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le {\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })+3<\frac{5n}{4}.$ Hence we will assume that $T^{\prime }$ has no ${\gamma }_{\mathit{\text{qtdR}}}(T^{\prime })$-function that assigns at least 2 to v₄. This means that $T_{v_4}$ has the following properties: (i) v₄ has at most one leaf neighbor, (ii) v₄ at most one children with depth 1, (iii) at most two children with depth 2, and (iv) v₄ cannot be a support vertex and having a child with depth 1. All these facts together imply that ${\mathrm{\text{deg}}}_T(v_4)\le 4$. We consider the following situations.

1. v₄ is a support vertex and ${\mathrm{\text{deg}}}_T(v_4)=4$.

   Then v₄ has a child w₃ with depth 2 other than v₃. Let $v_4{w}_3{w}_2{w}_1$ be the pendant path in T containing v₄ and let w be the leaf neighbor of v₄. Let $T^{″}=T-\{v_i,w_i|1\le i\le 3\}$ and let $f^{″}$ be a ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})$-function. Clearly $n(T^{″})\ge 4$ and $f^{″}(v_4)+f^{″}(w)\ge 2$. In this case, the function g defined by g(w) = 1, $g(v_4)=\mathrm{\text{max}}\{2,f^{″}(v_4)\},g(v_1)=g(w_1)=1$, $g(v_2)=g(w_2)=2,g(v_3)=g(w_3)=0$, and $g(x)=f^{″}(x)$ otherwise, is a QTDRD-function of T leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5(n-6)}{4}+7<\frac{5n}{4}$.

2. v₄ is a support vertex and ${\mathrm{\text{deg}}}_T(v_4)=3$.

   Let $T^{″}=T-T_{v_4}$ and let w be the leaf neighbor of $v_4.$ Since v₂ has been chosen with maximum degree on the diametral path, $n(T^{″})\ge 2.$ Now, if $n(T^{″})\in \{2,3\}$, then it can be seen that ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})<\frac{5n}{4}$. Hence we assume that $n(T^{″})\ge 4$. By the induction hypothesis on $T^{″},{\gamma }_{\mathit{\text{qtdR}}}(T^{″})\le \frac{5(n-5)}{4}$. Since any ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})$-function can be extended to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})+6$ by assigning 2 to $v_1,v_3,w$, and 0 to v₄, v₂, we obtain ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$.

3. ${\mathrm{\text{deg}}}_T(v_4)=4$ and v₄ has a child z₂ with depth 1 and degree 2.

   Let z₁ be the leaf neighbor of z₂. Since ${\mathrm{\text{deg}}}_T(v_4)=4,$ v₄ has a child $w_3\ne v_3$ with depth 2. Let $v_4{w}_3{w}_2{w}_1$ be the pendant path of T containing $v_4,$ and consider the tree $T^{″}=T-\{v_i,w_i|1\le i\le 3\}$. Clearly $n(T^{″})\ge 4$ and $T^{″}$ has a ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})$-function $f^{″}$ such that $f^{″}(v_4)+f^{″}(z_1)+f^{″}(z_2)\ge 3$. It can be seen that the function g defined by $g(v_4)=\mathrm{\text{max}}\{2,f^{″}(v_4)\},g(v_1)=g(w_1)=1,g(z_1)=g(v_2)=g(w_2)=2,g(z_2)=g(v_3)=g(w_3)=0$, and $g(x)=f^{\prime }(x)$ otherwise, is a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})+7$ leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5(n-6)}{4}+7<\frac{5n}{4}$.

4. ${\mathrm{\text{deg}}}_T(v_4)=3$ and v₄ has a child z₂ with depth 1 and degree 2.

   Let z₁ be the leaf neighbor of z₂, and consider the tree $T^{″}=T-T_{v_4}$. Note that $n(T^{″})\ge 2.$ Now if $n(T^{″})\in \{2,3\}$, then one can easily see that ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$. Hence let $n(T^{″})\ge 4$. By the induction hypothesis on $T^{″},$ ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})\le \frac{5(n-6)}{4}$. Since any ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})$-function can be extended to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})+7$ by assigning 2 to $v_2,v_4,z_1$, a 1 to v₁ and a 0 to v₃, z₂, leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$.

5. ${\mathrm{\text{deg}}}_T(v_4)=4$ and v₄ has a child z₂ with depth 1 and degree 3.

   According to item (ii) above, v₄ must belongs to a pendant path $v_4{w}_3{w}_2{w}_1$ such that $w_3\ne v_3.$ In this case, consider the tree $T^{″}=T-\{v_i,w_i|1\le i\le 3\}$ and let $f^{″}$ be a ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})$-function such that $f^{″}(z_2)=3$ and $f^{″}(v_4)$ is as large as possible. Clearly $n(T^{″})\ge 4$ and $f^{″}(v_4)+f^{″}(z_2)\ge 4$. Then the function g defined onV(T) by $g(z_2)=3,g(v_4)=\mathrm{\text{max}}\{2,f^{\prime }(v_4)\},g(v_1)=g(w_1)=1,g(v_2)=g(w_2)=2,g(v_3)=g(w_3)=0$, and $g(x)=f^{″}(x)$ otherwise, is a QTDRD-function of T of weight at most ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})+7$ leading to ${\gamma }_{\mathit{\text{qtdR}}}(T)\le \frac{5(n-6)}{4}+7<\frac{5n}{4}$.

6. ${\mathrm{\text{deg}}}_T(v_4)=3$ and v₄ has a children z₂ with depth 1 and degree 3.

   Let $T^{″}=T-T_{v_4}$ and note that $n(T^{″})\ge 2.$ If $n(T^{″})\in \{2,3\}$, then one can easily see that ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$. Hence let $n(T^{″})\ge 4$. By the induction hypothesis on $T^{″},$ ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})\le \frac{5(n-7)}{4}$. Since any ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})$-function can be extended to a QTDRD-function of T of weight ${\gamma }_{\mathit{\text{qtdR}}}(T^{″})+8$ by assigning 3 to z₂, 2 to v₄, v₂, 1 to v₁ and 0 to v₃ as well as the two leaf neighbors of z₂, it follows that ${\gamma }_{\mathit{\text{qtdR}}}(T)<\frac{5n}{4}$.

This completes the proof. □

In [18], Shao et al. showed that for any tree T of order n, ${\gamma }_{\mathit{\text{tdR}}}(T)\le \frac{3}{2}n$ with equality if and only if T is a corona of some tree $T^{\prime }.$ This result and the bound of Theorem 20 show that the difference between total double Roman domination and quasi total double Roman domination numbers can be arbitrary large.

Let $\mathcal{F}$ be a family of graphs that are obtained by from k disjoint paths $P_4^i=u_i^1{u}_i^2{u}_i^3{u}_i^4(k\ge 1)$ by adding edges between the $u_i^2$’s so that the resulting graph is connected. The proof of the following theorem can be found in [3].

Theorem 21.

For any connected graph of order $n\ge 4$, $${\gamma }_{\mathit{\text{dR}}}(G)\le \frac{5}{4}n.$$

The equality holds if and only if $G\in \mathcal{F}\cup \{\mathit{\text{cor}}(C_4)\}$.

The proof of the next corollary is similar to the proof of Corollary 19 and thus it is omitted.

Corollary 22.

If $G\in \mathcal{F}\cup \{\mathit{\text{cor}}(C_4)\}$, then ${\gamma }_{\mathit{\text{qtdR}}}(G)=\frac{5}{4}n.$

Theorem 23.

For any connected graph of order $n\ge 4$, $${\gamma }_{\mathit{\text{qtdR}}}(G)\le \frac{5}{4}n.$$

The equality holds if and only if $G\in \mathcal{F}\cup \{\mathit{\text{cor}}(C_4)\}$.

Proof.

Let T be an arbitrary spanning tree of G. Since adding an edge do not increase the quasi total double Roman domination, by Theorem 20 we obtain ${\gamma }_{\mathit{\text{qtdR}}}(G)\le {\gamma }_{\mathit{\text{qtdR}}}(T)\le (5n)/4,$ as desired. Moreover, if $G\in \mathcal{F}\cup \{\mathit{\text{cor}}(C_4)\}$, then Corollary 22 implies that ${\gamma }_{\mathit{\text{qtdR}}}(G)=(5n)/4$.

To prove the converse, assume that ${\gamma }_{\mathit{\text{qtdR}}}(G)=\frac{5}{4}n$. If $G=\mathit{\text{cor}}(C_4)$, then we are done. Hence assume that $G\ne \mathit{\text{cor}}(C_4)$ and let T be an arbitrary spanning tree of G. Then we have $T\in \mathcal{T}$ and so T is obtained from $k=n/4$ disjoint paths $P_4^i=u_i^1{u}_i^2{u}_i^3{u}_i^4(k\ge 1)$ by adding k – 1 edges between the $u_i^2$’s so that the resulting graph is connected. First we show that every leaf of T is a leaf in G. Suppose not, and let ${\mathrm{\text{deg}}}_G(u_i^1)\ge 2$ for some i. If $u_i^1{u}_i^3\in E(G)$, then the function f defined by $f(u_i^3)=3,f(u_i^4)=1,f(u_j^3)=f(u_j^1)=2,f(u_j^4)=1$ for $j\ne i$ and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than $\frac{5n}{4}$, a contradiction. If $u_i^1{u}_i^4\in E(G)$, then the function f defined by $f(u_i^3)=f(u_i^1)=2,f(u_j^3)=f(u_j^1)=2,f(u_j^4)=1$ for $j\ne i$ and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than $\frac{5n}{4}$, a contradiction again. If $u_i^1{u}_r^1\in E(G)$ or $u_i^1{u}_r^3\in E(G)$ for $r\ne i$, then the function f defined by $f(u_i^2)=f(u_i^4)=2,f(u_j^3)=f(u_j^1)=2,f(u_j^4)=1$ for $j\ne i$ and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than $\frac{5n}{4}$, a contradiction again. If $u_i^1{u}_r^2\in E(G)$ or $u_i^1{u}_r^4\in E(G)$ for $r\ne i$, then the function f defined by $f(u_i^2)=f(u_i^4)=2,f(u_j^4)=f(u_j^2)=2$, $f(u_j^1)=1$ for $j\ne i$ and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than $\frac{5n}{4}$, a contradiction. Therefore, every leaf of T is a leaf in G.

Next we show that ${\mathrm{\text{deg}}}_G(u_i^3)=2$ for each i. Suppose that ${\mathrm{\text{deg}}}_G(u_i^3)\ge 3$ for some i. If $u_i^3{u}_r^2\in E(G)$ for $r\ne i$, then the function f defined by $f(u_i^1)=f(u_i^4)=2$, $f(u_j^2)=f(u_j^4)=2,f(u_j^1)=1$ for $j\ne i$ and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than $\frac{5n}{4}$, a contradiction. Finally, assume that $u_i^3{u}_r^3\in E(G)$ for $r\ne i$. Since $G\ne \mathit{\text{cor}}(C_4)$, we may assume that ${\mathrm{\text{deg}}}_T(u_i^2)\ge 4$. Then the function f defined by $f(u_i^1)=f(u_i^4)=2,f(u_r^1)=f(u_r^3)=2,f(u_r^4)=1,f(u_j^2)=f(u_j^4)=2$, $f(u_j^1)=1$ for every $j\notin \{i,r\}$ and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than $\frac{5n}{4}$, a contradiction. Hence ${\mathrm{\text{deg}}}_G(u_i^3)=2$ for each i, implying that $G\in \mathcal{F}$ and the proof is complete. □

During the submission of this paper, Akhoundi, Khan, Shafi and Volkmann [2] recently established an upper bound for Quasi total double Roman domination of trees in terms of order and the number of support vertices.