Abstract
A quasi total double Roman dominating function (QTDRD-function) on a graph is a function 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 , 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 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 . Moreover, we establish an upper bound on the quasi total double Roman domination number and we characterize the connected graphs attaining this bound.
MATHEMATICS SUBJECT CLASSIFICATION:
1 Introduction
All graphs considered in this article are finite, undirected, simple and without isolated vertices. Let be a graph of order . For any vertex , the open neighbourhood of v is the set and the closed neighbourhood of v is the set . For a set , the open neighbourhood of S is and the closed neighbourhood of S is .
We denote the degree of a vertex v in a graph G by , or simply by if the graph G is clear from the context. Let and 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 Pn, Cn, and Kn while and denote the complete bipartite graph and double star of order m + n and , 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 and with , let be a tree obtained from a star by subdividing t edges exactly once. We say is a wounded spider if and and it is a healthy spider if r = 0 and . The center vertex of 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 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 A rooted tree T distinguishes one vertex r called the root. For each 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 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 Tv. 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 a new vertex and the edge .
Roman domination is a variation of domination that was formally introduced in graph theory, by Cockayne et al. [Citation11] 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 [Citation8–10].
In 2016, Beeler et al. defined a new variant of Roman domination in [Citation3], namely double Roman dominating functions. A function 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 . The double Roman domination number equals the minimum weight of a DRD-function on G. A DRD-function of G with weight is called a -function or -function of G. For a DRD-function f, let Vi be the set of vertices assigned the value i, where In that case, the function f will simply be referred to For more details on double Roman domination and its variations, see for example [Citation1, Citation17, Citation20].
In 2020, Hao et al. [Citation13] considered DRD-functions f such that the subgraph of G induced by the set has no isolated vertices, and call such functions total double Roman dominating functions, TDRD-functions. The total double Roman domination number is the minimum weight of a TDRD-function on G. For more details, see also [Citation14, Citation18, Citation19].
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 . It is quite straightforward to note that any TDRD-function on G is a QTDRD-function leading to (1) (1)
It is worth mentioning that the quasi total version for Roman dominating functions has been introduced by Cabrera Martínez et al. [Citation4] and has been further studied in [Citation5, Citation12, Citation16].
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 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 [Citation1].
Proposition 1.
For ,
Moreover, the function f defined by for and f(x) = 0 for the remaining vertices, is the unique -function when .
Proposition 2.
For ,
Moreover, the functions fj defined by for and for the remaining vertices, for , are the only -functions when .
Theorem 3.
For
Proof.
Let be a path of order n. Define the function h on by for and h(x) = 0 otherwise if n is odd and by for and h(x) = 0 for other vertices x, when n is even. It is easy to verify that h is a QTDRD-function of Pn of weight n + 1, leading to .
Furthermore, if , then since the unique -function is not a QTDRD-function of Pn we have For the remaining situations, it follows from Inequality (1) and Proposition 1 that . Therefore in either case . □
Theorem 4.
For ,
Proof.
Let be a cycle on n vertices. Define the function f on by for each and f(x) = 0, otherwise. It is easy to see that f is a QTDRD-function of Cn of weight and thus when n is even and when n is odd.
Furthermore, if n is even, then it follows from Inequality (1) and Proposition 2 that . If , then Inequality (1) and Proposition 2 implies that and so . Finally, assume that . Clearly, none of the functions fj is a QTDRD-function of Cn implying that , and thus . □
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 [Citation15], 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 . 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 are literals over U. The literal u is true under t if and only if the literal is false under t, and of course the literal 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 of clauses over U is satisfiable if and only if there exists some truth assignment for U that simultaneously satisfies all the clauses in . Such a truth assignment is called a satisfying truth assignment for . The 3SAT is specified as follows.
3-satisfiability problem (3SAT):
Instance: A collection of clauses over a finite set U of variables such that for .
Question: Is there a truth assignment for U that satisfies all the clauses in ?
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 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 and let be an arbitrary instance of 3SAT. We construct a bipartite graph G and chose a positive integer k such that if and only if is satisfiable. The construction of G is as follows.
For each variable , we associate a complete bipartite graph with bipartite sets and . For each clause , we associate a single vertex cj and we add the edge set if and if . Clearly, G is a bipartite graph of order , and of course the construction can be accomplished in polynomial time (). All that remains to be shown is that is satisfiable if and only if . This aim can be fulfilled by proving the following claims.
Claim 1. . Moreover, if , then for any γqtdR-function on G, and for each , while for each .
Proof of Claim 1. Let be a -function. By the construction of G, we have for each i, and therefore .
Suppose now that . Then for each and so . Also, it is clear that for each . Now if or and ( and is similar), then , this implies that , a contradiction. Moreover, if , then and so , a contradiction again. Therefore for each , and the proof of the claim is complete. ◆
Claim 2. if and only if is satisfiable.
Proof of Claim 2. Suppose that and let be a -function. By Claim 1, for each and . Define a mapping by (2) (2)
Arbitrarily choose a clause . Then there exits some such that cj is adjacent to either or to . Suppose, without loss of generality, that and . Since and , we have by (2), implying that the clause Cj is satisfied by t. Because of the arbitrariness of j with is satisfiable.
Conversely, suppose that is satisfiable, and let be a satisfying truth assignment for . First, construct a subset D of vertices of G as follows. If , then put the vertices ui and xi into D; if , then put the vertices and xi into D. Then define the function g on V(G) by g(x) = 3 for every and g(y) = 0 for any Since t is a satisfying truth assignment for , the corresponding vertex cj 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 . The equality follows from Claim 1, that is, . ◆
This completes the proof. □
3 Graphs G with small or large
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, Therefore, we start by characterizing connected graphs G for which Let us recall that the join 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 . Then
if and only if
if and only if or , where H is any graph.
if and only if G is a graph obtained from , by removing exactly one edge between and H, where H is a graph with .
Proof.
Let be a -function on G, and note that .
(i) Assume that . Then and by the definition of a QTDRD-function on G, we must have and Hence and thus . For the converse, clearly if , then .
(ii) Assume now that . Then one of the following situations holds:
and ;
and ;
and .
If (1) holds, let Then each vertex of must be adjacent to v and thus . If (2) holds, then and so , implying again that . Finally, assume that (3) holds and let . Then each vertex in is adjacent to both vertices v and u. If , then , while if , then clearly where .
Conversely, if , then . If then to avoid the previous case, we can assume that . By item (i), . The equality follows by assigning 2 to the vertices of and 0 to those of H.
(iii) Assume that , where and e is an edge with an endvertex belonging to and the other endvertex belongs to Let and such that By items (i) and (ii) . To get the equality, consider the function g on V(G) defined by g(w) = 1 and g(x) = 0 for . Clearly, g is a QTDRD-function of G with weight 5 and hence .
Conversely, let . Using the fact that it can be seen that the only case to be considered is and , and the other cases will be excluded because they lead us to have . Let and . By definition u and v are adjacent to all vertices in and w is adjacent to one of vertices u and v, say u. Since , by item (ii), where . Consequently, and the proof is complete. □
The next results are immediate consequences of Proposition 7.
Corollary 8.
For any graph of order .
Corollary 9.
Let be the complete r-partite graph with and of order .
If , then ;
If , then .
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,
This bound is sharp for stars and with and .
Proof.
Let v be a vertex with maximum degree and let w be a neighbor of v. It can be seen that is a QTDRD-function of G with weight . Thus . □
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 with , then .
Proof.
Let v be a vertex of G. Assume that and let . Since , we have . If each vi has a neighbor in X, then the function g given by g(x) = 2 for and g(x) = 0 otherwise, is a QTDRD-function of G of weight , as desired. Hence assume that for some i, say i = k. Since G is regular, we deduce that each component of has order at least two. Now, if and has maximum degree in , then the function g defined by g(v) = 3, , g(x) = 2 for and g(x) = 0 otherwise, is a QTDRD-function of G of weight , as desired. Hence we assume that , and thus each component of is isomorphic to K2. Since vk has no neighbor in X, each vertex in X is adjacent to all vertices in N(v) but vk. Let be the vertices of a K2-component of . Then the function g defined by g(v) = 2, , for and g(x) = 0 otherwise, is a QTDRD-function of G of weight at most , as desired. This completes the proof. □
Proposition 12.
If G is a connected graph of order with , then
Proof.
Let v be a vertex of G with maximum degree and . Since , we have . If each vi has a neighbor in X, then as in the proof of Proposition 11 we have . Hence we assume, without loss of generality, that for some i, say . If , then the same argument used in the proof of Proposition 11 leads to . Hence we assume that . Note that any isolated vertex in is of degree since as assumed has no neighbor in X. Now if has two isolated vertices u and , then u and must be adjacent to all vertices in and thus the function g defined by , g(x) = 2 for and g(x) = 0 otherwise, is a QTDRD-function of G of weight at most , as desired. Henceforth, we assume that has at most one isolated vertex. If , then clearly and assigning a 2 to v and the unique vertex of X, a 1 to and a 0 to the remaining vertices provides a QTDRD-function of weight . Therefore, we can assume that , and thus has a K2-component, say . Then the function g given by , g(x) = 2 for and g(x) = 0 otherwise, is a QTDRD-function of G of weight at most and the proof is complete. □
If G is a connected graph with , then and . Hence the next results are immediate consequences of Proposition 10.
Corollary 13.
For any connected graph G of order with equality if and only if
Proof.
Since G is connected and , we have . If , then Proposition 10 leads to Hence let . Then G is a path Pn or a cycle Cn. If , then by Theorem 3 we have with equality if n = 3, that is . If , then by Theorem 4 we have with equality if n = 3, that is . □
Using a similar argument as above we get the following.
Corollary 14.
The path P4 is the only connected graph G of order satisfying
Proposition 15.
Let G be a connected graph of order such that Then with equality if and only if , where G1, G2 and G – 3 are the graphs depicted in .
Proof.
If , then Proposition 10 leads to Hence . If , then and by Theorem 3, with equality if and only if n = 5, that is , while by Theorem 4, with equality if and only if , that is . Hence, in the sequel we can assume that . By Proposition 10, , and the bound follows.
Assume now that Let v be a vertex with degree 3 and let and . If there is an edge , then the function f defined on V(G) by f(v) = 3, , , f(x) = 1 and f(z) = 2 otherwise, is a QTDRD-function of G of weight , a contradiction. Hence no two vertices in X are adjacent. If v1 has at least two neighbors in X, then the function f defined on V(G) by , f(x) = 0 for and f(z) = 2 otherwise, is a QTDRD-function of G of weight yielding a contradiction. Hence v1 has at most one neighbor in X, and likewise for v2 and Moreover, since G is connected, each vertex in X must have a neighbor in N(v) implying that . If , say , then, without loss of generality, let for every In this case, G has order 7 and the function g defined by , and is a QTDRD-function of G of weight leading to a contradiction. If , say , then we may assume that and the function g defined by and is a QTDRD-function of G of weight a contradiction too. Hence . Now if , then it follows from Corollary 14 that . Finally, assume that and let . Since G is connected, let . If , then the function g defined by , and , is a QTDRD-function of G of weight a contradiction. Thus and similarly implying that u is a leaf. If , then the function g defined by , g(u) = 1 and , is a QTDRD-function of G of weight a contradiction. Hence and likewise . It follows that .
If , then it is easy to see that and the proof is complete. □
Proposition 16.
Let G be a connected graph G of order such that . Then with equality if and only if , where are the graphs depicted in .
Proof.
The bound follows from Corollaries 13, 14, and Proposition 15. Assume now that . As in the proof of Proposition 15, we may assume that . If , then , and one can easily check by Theorem 3 that and by Theorem 4 no cycle satisfies In the sequel, we can assume that . Consider a vertex v of degree 3 and let and . If v1 has two neighbors in X, then the function f defined on V(G) by f(v) = 3, , , f(x) = 0 for and f(z) = 2 otherwise, is a QTDRD-function of G of weight a contradiction. Hence each vi has at most one neighbor in X. If there are two edges in sharing a same endvertex, say xy, xz, then the function f defined on V(G) by f(v) = 3, , f(x) = 0 and f(a) = 2 otherwise, is a QTDRD-function of G of weight a contradiction. Hence we assume that . If has two disjoint K2-components, say and , then the function f defined on V(G) by f(v) = 3, and f(a) = 2 otherwise, is a QTDRD-function of G of weight a contradiction too. Therefore, has at most one K2-component. Consider the following two cases.
Case 1. has a K2-component, say .
Since G is connected and each vi has at most one neighbor in X, we deduce that . Assume first that , and without loss of generality, let for each i. Then the function g defined by for , g(w) = 1 and for every , is a QTDRD-function of G of weight a contradiction. Assume now that , where without loss of generality, for Then the function g defined by for i = 1, 2, and for i = 1, 2, is a QTDRD-function of G of weight a contradiction. Therefore that is , where If u1 is adjacent to v2 or v3, say v2, then assigning 2 to , 1 to and 0 to v1 and v2 provides a QTDRD-function of G of weight 6 which leads to a contradiction. Hence . If w is adjacent to v2 and then assigning a 2 to and w, a 0 to v2, v3 and u1 provides a QTDRD-function of weight a contradiction. Hence w is adjacent to at most one of v2 and Recall that each vertex of N(v) is adjacent to at most one vertex of X, and hence Now because of its degree, v1 is adjacent to at most one of v2 and If then for otherwise assigning a 2 to and a 0 to and u1 provides a QTDRD-function of weight a contradiction. Similarly it can be seen that and thus . In the next, we assume that that is w is a leaf. In this case, it is not hard to see that .
Case 2. has no K2-component.
Since G is connected and each vi has at most one neighbor in X, . As in the proof of Proposition 15, it can be seen that if we can construct a QTDRD-function of G of weight . Hence and of course (because of ). If , then let , and thus . Finally, let and assume that for i = 1, 2. It is not hard to see that . This completes the proof. □
4 An upper bound
In this section, we show that for any connected graph G with order , . 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 [Citation3].
Observation 17.
If v is a strong support vertex of a graph G, then there exists a -function f that assigns 3 to v and 0 to every leaf neighbor of v.
Let be a family of trees which obtained from k paths by adding k – 1 edges between s such that the resulting graphs is connected (see for k = 3). The proof of the following theorem can be found in [Citation3].
Theorem 18
([Citation3]). For any tree T of order with equality if and only if .
Corollary 19.
If is a tree of order n, then .
Proof.
Assume that , and let us use the same labeling of vertices described for the construction of T. Note that Then assigning a 2 to and for every i, a 1 to every and a 0 to the remaining vertices provides a QTDRD-function of T of weight leading to Moreover, by (1) and Theorem 18, we obtain and thus . □
Theorem 20.
Let T be a tree of order . Then with equality if and only if .
Proof.
Let T be a tree of order . We will proceed by induction on the order n. If n = 4, then and clearly with equality if and only if which belongs to . This establishes the base case. Let and assume that if is a tree of order , where and , then with equality if and only if . 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 . Hence, we may assume that T is not a star and thus . If , then T is a double star , where and . 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 . Hence, we can assume that , for otherwise the desired result follows.
If T has a support vertex x with at least three leaf neighbors, then consider the tree obtained from T by removing one leaf neighbor of x, say y. Observe that x remains a strong support vertex in . By Observation 17, x is assigned 3 under some γqtdR-function f on and such a -function can be extended to a QTDRD-function of T by assigning a 0 to y, leading to . Therefore, we can assume that every support vertex in T is adjacent to one or two leaves.
Let be a diametral path of T chosen such that is as large as possible. Note that v2 is a support vertex and thus Root T at vk, and consider the following cases.
Case 1. .
Thus v2 has exactly two leaf neighbors. Let , and note that has order since . If then T is a tree obtained from the path by adding a vertex u and an edge . In this case, assigning 3 to v2 and v4, 1 to v3 and 0 to every leaf of T provides a QTDRD-function of T with weight 7, and thus . Hence, we may assume that . Applying the induction hypothesis on , we have . Now, if there exists a γqtdR-function of such that , then can be extended to a QTDRD-function of T by assigning 3 to v2 and 0 to its two leaf neighbors, yielding . Henceforth, we may assume that every -function of assigns 0 to v3. According the choice of v2 on the diametral path, let s be the number of children of v3, with degree 3, other than v2, r be the number of children of v3 with degree 2 and t be the number of leaf neighbors of v3 in T. Observe that if (resp. ), then v3 would be assigned a 3 (resp. 2) under some γqtdR-function of , contradicting our earlier assumption. Hence and . Similarly, if , then v3 could be assigned at least 1 under some γqtdR-function of , contradicting our earlier assumption again. Hence s = 0.
Assume first that Let denote the leaf neighbor of v3, and let be a γqtdR-function of . By our earlier assumption we have and thus . If r = 1, then . In this case, form f from -function , by letting for all for the leaf neighbor of the child of v3 with degree 2 and f(z) = 0 for the remaining vertices of Then f is a QTDRD-function of T, leading to . If r = 0, then let . Since , has order . If , then T is isomorphic to the tree T1 depicted in and it is easy to see that , as desired. If , then T is one of the two trees illustrated in , and it is easy to see that , as desired. Hence, we may assume that . Applying the induction hypothesis on , we have . Since any -function can be extended to a QTDRD-function of T by assigning 3 to the vertices v2 and v3, and 0 to each leaf at we get
Now, assume that t = 0, and let be tree obtained from T by deleting v3 and its descendants, that is . Note that Since has order . If , then we have two possible trees, either T is obtained from two disjoint paths P5 and P3 by adding an edge between their centers or T is a obtained from a path P5 by adding a new vertex attached to a support vertex of the path P5. In either case, it can be seen that Now, if then T is isomorphic to one of the trees illustrated in and it can be seen that each of these four trees T satisfies Consequently, we can assume in the next that . Applying the induction hypothesis on , we have . Let be a -function. If r = 0, then we extend to a QTDRD-function of T of weight by assigning 3 to v2, 1 to v3 and 0 to the two leaf neighbors of v2. If r = 1, then we extend to a QTDRD-function of T of weight by assigning 3 to the two children of v3, 1 to v3 and 0 to all leaves of . Each case leads to .
Case 2. .
By the choice of the diametral path, each child of v3 has degree at most two. Let r be the number of children of v3 with degree 2 and t be the number of leaves adjacent to v3. Note that and Let be the tree obtained from T by deleting v3 and all its descendants. Since has order . If then and so
Since and , we get . If , then T is a tree belonging to the two families of trees illustrated in and so . If , then it can be seen that
while, if , then
In either case, we have , as desired. Therefore, we may assume in the next that . Applying the induction hypothesis on , we have . Now, if , then any -function , can be extended to a QTDRD-function of T of weight by assigning 3 to v3, 2 to every leaf neighbor of not adjacent to 1 to one leaf neighbor of v3 and 0 to the remaining vertices of . It follows that as desired. Assume now that t = 1. Then any -function can be extended to a QTDRD-function of T of weight by assigning 2 to v3 and all leaves of that are not adjacent to 1 to the unique leaf neighbor of v3 and 0 to the remaining vertices of . It follows that as desired.
Further if then we have equality throughout the previous inequality chain. In particular, we have r = 1 and . Thus by the induction hypothesis on . Hence we can assume that obtained by from k paths by adding k – 1 edges between ’s such that the resulting graph is connected. Without loss of generality, assume that and let w denote the unique leaf neighbor of If (the case is similar), then the function f defined on V(T) by for , f(w) = 1, and f(x) = 0 otherwise, is a QTDRD-function of T of weight less than a contradiction. If , then the function f defined on V(T) by for , f(w) = 1, and f(x) = 0 otherwise, is a QTDRD-function of T of weight less than a contradiction again. Therefore, and so .
Now, let t = 0. If , then form f from any by assigning 2 to v3 and to each leaf at distance two from v3 in and 0 to the children of v3. Using the induction hypothesis on it follows that as desired. Hence we can assume in the sequel that .
First let and consider tree obtained from T by removing the set of vertices . If , then by the choice of the diametral path, we have and clearly . Hence assume that . By the induction hypothesis on . Now, if , then noting that any -function can be extended to a QTDRD-function of T of weight by assigning 2 to v4, v2, 1 to v1 and 0 to v3, we get . Thus suppose that . By the induction hypothesis , and thus obtained from k paths by adding k – 1 edges between ’s so that the resulting graph is connected. Further, we may assume that Note that assigning 2 to ’s and ’s, 1 to every and 0 to all ’s provides a -function, say g. Now, if , then g can be extended to a QTDRD-function of T of weight by assigning 2 to v3, v1 and 0 to v4, v2, leading to . If , then we can reassign the values on so that these two vertices receive 2 which leads to a contradiction as above.
Finally we can assume that . Observe that if we consider the tree such that there is a -function which assigns at least 2 to v4, then such a function can be extended to QTDRD-function of T by assigning 2 to 1 to v1 and 0 to v3 leading to Hence we will assume that has no -function that assigns at least 2 to v4. This means that has the following properties: (i) v4 has at most one leaf neighbor, (ii) v4 at most one children with depth 1, (iii) at most two children with depth 2, and (iv) v4 cannot be a support vertex and having a child with depth 1. All these facts together imply that . We consider the following situations.
v4 is a support vertex and .
Then v4 has a child w3 with depth 2 other than v3. Let be the pendant path in T containing v4 and let w be the leaf neighbor of v4. Let and let be a -function. Clearly and . In this case, the function g defined by g(w) = 1, , , and otherwise, is a QTDRD-function of T leading to .
v4 is a support vertex and .
Let and let w be the leaf neighbor of Since v2 has been chosen with maximum degree on the diametral path, Now, if , then it can be seen that . Hence we assume that . By the induction hypothesis on . Since any -function can be extended to a QTDRD-function of T of weight by assigning 2 to , and 0 to v4, v2, we obtain .
and v4 has a child z2 with depth 1 and degree 2.
Let z1 be the leaf neighbor of z2. Since v4 has a child with depth 2. Let be the pendant path of T containing and consider the tree . Clearly and has a -function such that . It can be seen that the function g defined by , and otherwise, is a QTDRD-function of T of weight leading to .
and v4 has a child z2 with depth 1 and degree 2.
Let z1 be the leaf neighbor of z2, and consider the tree . Note that Now if , then one can easily see that . Hence let . By the induction hypothesis on . Since any -function can be extended to a QTDRD-function of T of weight by assigning 2 to , a 1 to v1 and a 0 to v3, z2, leading to .
and v4 has a child z2 with depth 1 and degree 3.
According to item (ii) above, v4 must belongs to a pendant path such that In this case, consider the tree and let be a -function such that and is as large as possible. Clearly and . Then the function g defined onV(T) by , and otherwise, is a QTDRD-function of T of weight at most leading to .
and v4 has a children z2 with depth 1 and degree 3.
Let and note that If , then one can easily see that . Hence let . By the induction hypothesis on . Since any -function can be extended to a QTDRD-function of T of weight by assigning 3 to z2, 2 to v4, v2, 1 to v1 and 0 to v3 as well as the two leaf neighbors of z2, it follows that .
This completes the proof. □
In [Citation18], Shao et al. showed that for any tree T of order n, with equality if and only if T is a corona of some tree 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 be a family of graphs that are obtained by from k disjoint paths by adding edges between the ’s so that the resulting graph is connected. The proof of the following theorem can be found in [Citation3].
Theorem 21.
For any connected graph of order ,
The equality holds if and only if .
The proof of the next corollary is similar to the proof of Corollary 19 and thus it is omitted.
Corollary 22.
If , then
Theorem 23.
For any connected graph of order ,
The equality holds if and only if .
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 as desired. Moreover, if , then Corollary 22 implies that .
To prove the converse, assume that . If , then we are done. Hence assume that and let T be an arbitrary spanning tree of G. Then we have and so T is obtained from disjoint paths by adding k – 1 edges between the ’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 for some i. If , then the function f defined by for and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than , a contradiction. If , then the function f defined by for and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than , a contradiction again. If or for , then the function f defined by for and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than , a contradiction again. If or for , then the function f defined by , for and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than , a contradiction. Therefore, every leaf of T is a leaf in G.
Next we show that for each i. Suppose that for some i. If for , then the function f defined by , for and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than , a contradiction. Finally, assume that for . Since , we may assume that . Then the function f defined by , for every and f(x) = 0 otherwise, is a QTDRD-function of G of weight less than , a contradiction. Hence for each i, implying that and the proof is complete. □
During the submission of this paper, Akhoundi, Khan, Shafi and Volkmann [Citation2] recently established an upper bound for Quasi total double Roman domination of trees in terms of order and the number of support vertices.
References
- Abdollahzadeh Ahangar, H., Chellali, M., Sheikholeslami, S. M. (2019). On the double Roman domination in graphs. Discrete Appl. Math. 103: 1–11.
- Akhoundi, M., Khan, A., Shafi, J., Volkmann, L. (2024). Quasi total double Roman domination in trees. Commun. Comb. Optim. 9: 159–168.
- Beeler, R. A., Haynes, T. W., Hedetniemi, S. T. (2016). Double Roman domination. Discrete Appl. Math. 211: 23–29.
- Cabrera García, S., Cabrera Martínez, A., Yero, I. G. (2019). Quasi-total Roman domination in graphs. Results Math. 74: 1–18.
- Cabrera, M. A., Hernandez-Gomez, J. C., Sigarreta, J. M. (2021). On the quasi total Roman domination number of graphs. Mathematics 9: 2823.
- Chellali, M., Jafari Rad, N., Sheikholeslami, S. M., Volkmann, L. (2020). Roman domination in graphs. In: Haynes, T. W., Hedetniemi, S. T., Henning, M. A., eds. Topics in Domination in Graphs. Berlin/Heidelberg: Springer, pp. 365–409.
- Chellali, M., Jafari Rad, N., Sheikholeslami, S. M., Volkmann, L. (2021). Varieties of Roman domination. In: Haynes, T. W., Hedetniemi, S. T., Henning, M. A., eds. Structures of Domination in Graphs. Springer: Berlin/Heidelberg, pp. 273–307.
- Chellali, M., Jafari Rad, N., Sheikholeslami, S. M., Volkmann, L. (2020). Varieties of Roman domination II. AKCE Int. J. Graphs Comb. 17: 966–984.
- Chellali, M., Jafari Rad, N., Sheikholeslami, S. M., Volkmann, L. (2022). The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory 42: 861–891.
- Chellali, M., Jafari Rad, N., Sheikholeslami, S. M., Volkmann, L. (2020). A survey on Roman domination parameters in directed graphs. J. Combin. Math. Combin. Comput. 115: 141–171.
- Cockayne, E. J., Dreyer, P. A., Hedetniemi, S. M., Hedetniemi, S. T. (2004). Roman domination in graphs. Discrete Math. 278: 11–22.
- Ebrahimi, N., Amjadi, J., Chellali, M., Sheikholeslami, S. M. (2023). Quasi-total Roman reinforcement in graphs. AKCE Int. J. Graphs Combin. 20: 1–8.
- Hao, G., Volkmann, L., Mojdeh, D. A. (2020). Total double Roman domination in graphs. Commun. Comb. Optim. 5: 27–39.
- Hao, G., Xie, Z., Sheikholeslami, S. M., Hajjari, M. (2023). Bounds on the total double Roman domination number of graphs. Discuss. Math. Graph Theory 43: 1033–1061.
- Garey, M. R., Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completness. San Francisco: Freeman.
- Mangal, V., Venkata Subba Reddy, P. (2022). Algorithmic aspects of quasi-total Roman domination in graphs. Commun. Comb. Optim. 7: 93–104.
- Poureidi, A. (2023). Double Roman domination in graphs: algorithmic complexity. Commun. Comb. Optim. 8: 491–503.
- Shao, Z., Amjadi, J., Sheikholeslami, S. M., Valinavaz, M. (2019). On the total double Roman domination. IEEE Access 7: 52035–52041.
- Teymourzadeh, A., Mojdeh, D. A. (2023). Covering total double Roman domination in graphs. Commun. Comb. Optim. 8:115–125.
- Yue, J., Wei, M., Li, M., Liu, G. (2018). On the double Roman domination of graphs. Appl. Math. Comput. 338: 669–675.