On the Total Version of Triple Roman Domination in Graphs

Academic Editor: Bo Zhou Received: 14 March 2025 Revised: 7 April 2025 Accepted: 8 April 2025 Published: 12 April 2025 Citation: Valenzuela-Tripodoro, J.C.; Mateos-Camacho, M.A.; Cera, M.; Alvarez-Ruiz, M.P. On the Total Version of Triple Roman Domination in Graphs. Mathematics 2025,13, 1277. https://doi.org/10.3390/ math13081277 Copyright: © 2025 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/ licenses/by/4.0/). Article On the Total Version of Triple Roman Domination in Graphs Juan Carlos Valenzuela-Tripodoro 1,* , Maria Antonia Mateos-Camacho 2, Martin Cera 3 and Maria Pilar Alvarez-Ruiz 1 1Escuela Técnica Superior de Ingeniería de Algeciras, Universidad de Cádiz, 11202 Algeciras, Spain; pilar[email protected] 2Escuela Internacional de Doctorado, Universidad de Sevilla, 41013 Sevilla, Spain; [email protected] 3 Escuela Técnica Superior de Ingeniería Agronómica, Universidad de Sevilla, 41005 Sevilla, Spain; [email protected] *Correspondence: [email protected]; Tel.: +34-956028063 Abstract: In this paper, we describe the study of total triple Roman domination. Total triple Roman domination is an assignment of labels from { 0,1,2,3,4 } to the vertices of a graph such that every vertex is protected by at least three units either on itself or its neighbors while ensuring that none of its neighbors remains unprotected. Formally, a total triple Roman dominating function is a function f:V(G)→ { 0,1,2,3,4 } such that f(N[v]) ≥ |AN(v)|+ 3, where AN(v) denotes the set of active neighbors of vertex v , i.e., those assigned a positive label. We investigate the algorithmic complexity of the associated decision problem, establish sharp bounds regarding graph structural parameters, and obtain the exact values for several graph families. Keywords: Roman domination; total Roman domination; triple Roman domination; total triple Roman domination MSC: 05C78 1. Introduction This study introduces a variation of the Roman domination problem in graphs. In previous works, we explored the [k] -Roman domination model, which involves defending against single attacks that require at least k units, focusing on the k= 3 case. In this work, we extend the model by ensuring that stronger vertices, i.e., those with some legion deployed on them, are not isolated. The Roman domination model originates from Emperor Constantine I’s defensive strategies [ 1 – 4 ]. His defensive strategy aimed to position the smallest possible number of legions across the empire while ensuring that each city housed between 0 and 2 legions. Cities without legions had to be adjacent to at least one city with two legions that could provide protection without remaining unprotected itself. This was first modeled by Cockayne et al. [ 5 ] in 2004. Since then, many variants have been studied to enhance its efficiency [6–10]. This model assigns labels { 0,1,2 } to cities based on the number of legions. A city labeled with 0 must be adjacent to a city labeled with 2 to ensure defense without leaving other cities unprotected. This defines a Roman dominating function (RDF), and its minimum weight is called the Roman domination number, γR(G). A total dominating set S in a graph G guarantees that any vertex has a neighbor in S . Liu et al. [ 11 ] introduced the total Roman domination number for graphs without isolated vertices, denoted γtR(G) , which minimizes the weight of an RDF, making sure that the set of vertices with a positive label form a total dominating set. Mathematics 2025,13, 1277 https://doi.org/10.3390/math13081277 Mathematics 2025,13, 1277 2 of 19 The double Roman domination, introduced by Beeler et al. [ 12 ], uses labels { 0,1,2, 3 } , ensuring that two legions can defend each city. Shao et al. [ 13 ] and Hao et al. [ 14 ] extended this to total double Roman domination, combining both conditions. Ahangar et al. [ 15 ] introduced the [k] -Roman domination model, focusing on the k= 3 case, called triple Roman domination. This assigns labels { 0,1, . . . , k+ 1 } to vertices such that each vertex with f(u)<k satisfies f(N[u]) ≥k+|AN(u)| , where AN(u) stands for the active neighbors (neighbors with a positive label) of u . The minimum weight of such a function is the [k] -Roman domination number, γ[kR](G) . Hajjari et al. [ 16 ] provided bounds, including γ[3R](G)≤3n 2for graphs with δ(G)≥2. The concept of total domination can be incorporated into the triple Roman domination model to prevent there being isolated vertices among labeled ones, strengthening the network at the potential cost of higher expense. A total triple Roman dominating function (t3RDF) satisfies both triple Roman domination and secures no isolated vertices in the induced subgraph by vertices with positive labels. The total triple Roman domination number, γ[t3R](G) , is the minimum weight of a t3RDF. This paper introduces the total triple Roman domination model. We examine the algorithmic complexity of the decision problem, provide bounds, describe extremal graphs, and find exact values for several graph families. The rest of this paper is organized as follows: Section 2establishes the necessary notation and preliminaries. In Section 3, we prove the NP-completeness of the associated decision problem, even for bipartite graphs. Section 4presents sharp bounds for the total triple Roman domination number in terms of structural parameters like maximum degree and girth. Section 5derives exact values for specific graph families, including paths and cycles. Finally, Section 6discusses the implications of our results and suggests future research directions. 2. Notation Throughout this paper, we consider simple, finite, and undirected graphs. Let G= (V,E) be a graph with vertex set V(G) and edge set E(G) . The order of a graph G is the number of vertices, denoted by |V(G)| , and the size of the graph is the number of edges. The degree of a vertex v , denoted dG(v) or simply d(v) when no confusion is possible, is the number of edges incident to v . The maximum degree and minimum degree of G are denoted by ∆(G) and δ(G) , respectively. The neighborhood of a vertex v in a graph G is the set of all vertices adjacent to v , denoted by N(v) . A vertex v is called an isolated vertex if it has no adjacent vertices, i.e., if its neighborhood is empty, N(v) = ∅ . The closed neighborhood of a vertex v is denoted by N[v] , and it is defined as N(v)∪ {v} . The induced subgraph G[S] of a graph G is formed by a subset S⊆V(G) of vertices, along with all edges in G that have both endpoints in S . A graph is regular if all of its vertices have the same degree, that is, it is k -regular if each vertex has degree k . A universal vertex in a graph is a vertex that is adjacent to all other vertices in the graph, meaning its degree is |V(G)| − 1, where |V(G)| is the number of vertices in the graph. Apath Pn on length n− 1 is a graph with n vertices arranged in a linear sequence, where each vertex (except the endpoints) has a degree of 2. A cycle Cn of length n is a graph with n vertices forming a closed path, where each vertex has a degree of 2. The girth of a graph is defined as the length of the shortest cycle in the graph. If no cycles exist, the girth is said to be infinite. The distance between two vertices u and v , denoted by d(u , v) , is the length of a shortest path with end-vertices u and v . A set of vertices that is a k -independent set is where every pair of vertices of the set are at a distance, as least k . The star graph S1,q consists of a central vertex adjacent to q leaves. A tree is a connected graph containing no Mathematics 2025,13, 1277 3 of 19 cycles. A graph is said to be connected if there is a path between every pair of vertices. From now on, we refer to a non-trivial connected graph as an ntc-graph. The complete graph Kn has an edge between every pair of vertices and the complete bipartite graph Kp,q consists of two disjoint sets of vertices of orders p and q , where each vertex in one set is adjacent to all vertices in the other set. Aleaf is a vertex of degree one. A weak support vertex is a vertex adjacent to a leaf, while a strong support vertex is a vertex adjacent to at least two leaves. The corona product of two graphs G and H , denoted by G◦H , is obtained by taking one copy of G , called the center graph, and a number of copies of H equal to the order of G . Then, each copy of H is assigned a vertex in G , and that one vertex is attached to each vertex in its corresponding Hcopy by an edge (see Figure 1). Figure 1. The corona product K4◦K2. Regarding domination in graphs, a dominating set (for short, d-set) of G is a set D⊆V(G) such that every vertex in V(G)\D has a neighbor in D . The domination number γ(G) is the minimum cardinality of a dominating set. A γ -set is a dominating set with cardinality equal to γ=γ(G) . A Roman dominating function on G (for short, RDF) is a function f:V(G)→ { 0,1,2 } such that every vertex with f(v) = 0 has a neighbor u with f(u) = 2. The Roman domination number (RDN) γR(G) is the minimum weight ∑v∈V(G)f(v) over all such functions. A [k] -Roman dominating function (kRDF) is a function f:V(G)→ { 0,1, . . . , k+ 1 } satisfying the stronger condition that every vertex v with f(v)<k has at least one neighbor u with f(N[u]) ≥k+|AN(u)| . A total triple Roman dominating function (t3RDF) is a 3RDF such that the set of vertices with a positive label induces an isolated-free subgraph. Analogously, the total triple Roman domination number (t3RDN) of a graph Gis denoted by γ[t3R](G). In Figure 2, we can find two total triple Roman dominating functions in a graph G . We may readily check that the one depicted on the right has the minimum weight. All notation follows the standard conventions in graph theory. 4 2 2 2 0 3 1 0 (a) A t3RD-function with weight 14. 0 4 4 0 0 22 0 (b) A t3RD-function with weight 12. Figure 2. Two different total triple Roman dominating functions. Mathematics 2025,13, 1277 4 of 19 3. Complexity The goal of this section is to prove that the total triple Roman domination decision problem (t3RDP) is NP-complete even for bipartite graphs. We prove this by showing the equivalence of any instance of the t3RDP with an instance of one of the Exact 3-Cover (X3C) problem. Formally, we consider the following decision problems: t3RDP PROBLEM Instance: Graph G= (V,E)and a positive integer K. Question: Does Ghave a t3RD function fwith f(V)≤K? X3C PROBLEM Instance: A finite set X,|X|=3q, and a collection Cof 3-element subsets of X. Question: Does there exist a subset C′⊆C such that every element of X appears in exactly one element of C′? Proposition 1. t3RDP is NP-complete for bipartite graphs. Proof. We can readily prove that t3RDP is in the NP-class because any potential solution can be verified in polynomial time. We now show that converting any instance of X3C to an instance of t3RDP results in equivalent solutions for both problems. Consider X={x1,x2, . . . , x3q} and C={C1 , C2 , . . . , Cr} , an instance (X , C) of X3C. For each xi∈X , we include a gadget Hi by adding two pendant vertices {p1 ik , p2 ik} to each vertex yik for k= 2,3,4 of the cycle {yi1 , yi2 , yi3 , yi4} . Additionally, for each Cj∈C , we construct the gadget Wjby adding two pendant vertices {q1 jl,q2 jl}to each vertex zjl of the path {zj1,zj2,zj3}. We construct the graph Γ=Γ(X , C) as follows: We start with a bipartite graph where the vertex set consists of X∪C . Each xi∈X is adjacent to a vertex Cj∈C if and only if xi is one of the three elements belonging to the 3-element subset Cj (i.e., Cj={xj1 , xj2 , xj3} and xi∈ {xj1 , xj2 , xj3} ). We then incorporate the gadgets Hi by adding an edge between xi and yi1 for i= 1, . . . ,3 q . Similarly, we attach the gadgets Wj to Γ by adding edges joining the vertices {Cj,zj1}and {Cj,zj3}, respectively, for j=1, . . . , r(see Figure 3). p1 i2 p2 i2 p2 i3 p1 i3 p2 i4 p1 i4 yi3 yi4yi2 yi1 xi x1x2xix3q · · · · · · · · ·· · · C1C2CjCr−1Cr q1 j1 q2 j1 q2 j2 q1 j2 p2 j3 q1 j3 Cj zj3zj1 zj2 Hi Wj Figure 3. Gadgets attached to xiand Cjwhen constructing the bipartite graph Γ. Clearly, the constructed graph is bipartite with vertex classes {xi,yi2,yi4,p1 i3,p2 i3: 1 ≤i≤3q} ∪ {zj1,zj3,q1 j2,q2 j2: 1 ≤j≤r} and {yi1,yi3,p1 i2,p2 i2,p1 i4,p2 i4: 1 ≤i≤3q} ∪ {Cj,zj2,q1 j1,q2 j1,q1 j3,q2 j3: 1 ≤j≤r}. Mathematics 2025,13, 1277 5 of 19 Now, assume that there exists C′⊆C , which is an exact cover for the set X . Let f be a function over the vertices of Γ, defined as follows: f(v) = 4 if v∈ {Cj:Cj∈C′} ∪ {yik: 1 ≤i≤3q, 2 ≤k≤4} ∪ {zjl: 1 ≤j≤r, 1 ≤l≤3} and f(v) = 0 otherwise. Since C′ is a solution of the X3C for the instance (X , C) , we may deduce that |C′|=q . On the other hand, f(N[v]) ≥ |AN(v)|+ 3 for all v∈V(Γ) and the induced subgraph by the set of vertices with a positive label has no isolated vertices. Hence, fis a t3RD function with w(f) = f(V(Γ)) = 40q+12r. To complete the proof, suppose that f is a t3RDF with f(V(Γ)) ≤ 40 q+ 12 r . Since f(yik) are support vertices and f is a t3RDF, we may assume that f(v) = 4 for all v∈ {yik: 1 ≤i≤ 3 q , 2 ≤k≤ 4 } . Analogously, without loss of generality, we may assume that f(v) = 4 for v∈ {zjl: 1 ≤j≤r, 1 ≤l≤3}. If f(yi1)= 0 for some 1 ≤i≤ 3 q , then we may define a new function f∗ as follows: f∗(yi1) = 0, f∗(Cji) = min{f(Cji) + f(yi1) ,4 } , where Cji is a clause containing xi . As the vertex yi1 is total triple dominated by any of the vertices yik , with k= 2,3,4, we have that f∗ is a t3RDF with weight at most f(V) . So, we may assume that f(yi1) = 0 for all i=1, . . . , 3q. Analogously, if f(xi)= 0 for some 1 ≤i≤ 3 q , the function f∗(xi) = 0, f∗(Cji) = min{f(Cji) + f(xi) ,4 } , where Cji is a clause containing xi . Since the vertices Cj are adjacent to both zjk , with k∈ { 1,3 } , then we have that f∗ is a t3RDF with weight at most f(V) . Then, we may assume that f(xi) = 0 for all i=1, . . . , 3q. In such a case, we have that f(V(Γ)) = 12 r+ 36 q+∑1≤j≤rf(Cj)≤ 40 q+ 12 r , which implies that ∑1≤j≤rf(Cj)≤4q. Let C′ be {Cj:f(Cj) = 4 } and suppose that |C′|=s<q . Then, the number of vertex xi∈X with a neighbor in C′ is at most 3 s . As a result, |xi:N(xi)∩C′=∅| ≥ 3 q− 3 s and f(N[xi]) ≥ |AN(xi)|+ 3 ≥ 5 for each vertex xi∈X without neighbours in C′ . Also, given that the cardinality of Cjis three, it must be that ∑ 1≤j≤r f(Cj) = ∑ Cj∈C′ f(Cj) + ∑ Cj∈C\C′ f(Cj) =4s+1 3∑ xi/∈N(C′) f(N[xi]) ≥4s+5 3(3q−3s) = 5q−s>4q, which is a contradiction. Therefore, |C′|=q with f(v) = 4 if v∈C′ and f(v) = 0 if v∈C\C′ . As f(xi) = 0 and f(yi) = 0 for all i , then there exist C′ ji∈C′ with xi∈C′ ji . Taking into account that |X|= 3 q and the cardinality of Cjis three, then the elements of C′are disjoint from each other. Hence, C′solves the instance (X,C)of the X3C problem. Although the proof of the result is lengthy, the key insight lies in constructing a bipartite graph associated with the decision problem. This graph is built from the elements xi∈X and the clauses Cj (3-element subsets {xj1 , xj2 , xj3} ), which establishes the equivalence between the existence of a solution to the X3C problem and the existence of a total triple Roman domination function with the given weight. Mathematics 2025,13, 1277 6 of 19 4. Bounds Once it is shown that calculating the exact value of the total triple Roman domination number (t3RDN) is NP-hard, it is a natural step forward to bound this parameter in terms of well-known structural features of a graph. Clearly, the t3RDN of a disconnected graph is the sum of the t3RDN of its components. As we have mentioned above, the total version of this domination problem only makes sense for isolated vertex-free graphs. Therefore, since we need any undefended vertex to be able to receive at least 3 units from its active neighbors, it is straightforward to derive a first upper bound by assigning a label of 2 to each vertex in the graph. Proposition 2. Let G be a connected graph of order n . Then, γ[t3R](G)≤ 2 n . Equality holds if and only if G is the corona product H ◦K1of a connected graph H with a K1. Proof. To prove the inequality, we consider f to be the function defined as f(v) = 2 for all v∈V(G). Clearly, fis a t3RDF and, therefore, γ[t3R](G)≤2n. Next, we characterize the graphs that attain equality. First, if G=H◦K1 and f is a γ[t3R](G) -function, then n=|V(G)| is an even integer and f(u) + f(v)≥ 4 for each leaf u , where v is the corresponding support vertex. Hence, γ[t3R](G) = w(f)≥4n 2=2nand the equality holds. On the other hand, suppose that γ[t3R](G) = 2 n= 2 |V(G)| . If n= 2, then G=K2=K1◦K1 and the result holds. So, we may assume that n≥ 3. If ∆(G) = n− 1, then γ[t3R](G)≤5, which is impossible because γ[t3R](G) = 2n. So, assume that ∆(G)≤n−2. Let v be a vertex with maximum degree in G and denote by N(v) = {z1 , . . . , z∆} its neighborhood. First, suppose that δ(G)≥ 2. If there exists a vertex w such that N(w)⊆N(v) , then consider such a vertex having the minimum degree and denote by N(w) = {zj1 , . . . , zjd(w)} its neighbors. Now, we may define a function f as follows: f(v) = 3; f(zj2) = . . . =f(zjd(w)) = 0; and f(x) = 2 otherwise. By our choice of w , every vertex labeled with a 2 is adjacent to a vertex with a positive label. The vertices with a label of 0 are adjacent to both v and w ; therefore, f is a t3RDF in G and γ[t3R](G)≤w(f) = 3 + 2 (n− 1 −(d(w)− 1 )) ≤ 3 + 2 (n− 1 −( 2 − 1 )) = 2 n− 1, a contradiction. If N(w)⊆ N(v) for all w∈V\N[v] , then we may define a function f as follows: f(v) = 3; f(z1) = 1, f(z2) = . . . =f(z∆) = 0; and f(x) = 2 otherwise. We can readily check that f is a t3RDF in G and, hence, γ[t3R](G)≤w(f)≤ 3 + 1 + 2 (n−∆(G)− 1 )≤ 2n−2, again a contradiction. So, we can deduce that it must be δ(G) = 1. If there exists a strong support vertex v such that {z1 , . . . , zp:p≥ 2 } are its leaves, then we can define a function f as follows: f(v) = 4; f(z1) = 1, f(z2) = . . . =f(zp) = 0; and f(x) = 2 otherwise. It is straightforward to check that f is a t3RDF, and then γ[t3R](G)≤w(f) = 5 + 2 (n−p− 1 )≤ 2 n− 1. Hence, there are only weak support vertices in G . If there exists a vertex v∈V(G) that is neither a leaf nor a support vertex, then we may define a function f as follows: f(v) = 1 and f(x) = 2 otherwise. Since d(v)≥ 2, then f is a t3RDF and γ[t3R](G)≤ 2 n− 1, which is not possible. Then, every vertex in G is either a leaf or a weak support vertex, which finishes the proof. Our next results give us an upper bound for the t3RDN in terms of the maximum degree of the graph. Proposition 3. Let G be an ntc-graph of order n and maximum degree ∆(G)≥ 2. Then, γ[t3R](G)≤3n−2∆(G). Mathematics 2025,13, 1277 7 of 19 Proof. Consider a vertex v∈V(G) with maximum degree ∆(G) and let N(v) = {zj:j= 1, . . . , ∆(G)} be the neighborhood of v . Let us define the function f:V→ { 0,1,2,3,4 } as follows: f(v) = 3, f(zj) = 1 for j= 1, . . . , ∆(G) and f(u) = 3 for the remaining vertices. Then, fis t3RDF and γ[t3R](G)≤w(f) = 3(n−∆(G)) + ∆(G) = 3n−2∆(G). Some graphs, including the path P3 and the cycle C3 , attain this bound. Furthermore, we can readily verify that the upper bound given in Proposition 3improves upon the one presented in Proposition 2whenever ∆(G)>n 2. Proposition 4. Let G be an ntc-graph of order n , δ(G)≥ 2, girth g≥ 5, and maximun degree ∆(G)≤n−2. Then, γ[t3R](G)≤2(n−∆(G) + 1). Proof. Consider a vertex v∈V(G) with maximum degree ∆(G) and let N(v) = {zj:j= 1, . . . , ∆(G)} be the neighborhood of v . Let us define the function f:V→ { 0,1,2,3,4 } as follows: f(v) = 3, f(z1) = 1, f(zj) = 0 for j=q and f(u) = 2 for the remaining vertices. Let z be any vertex belonging to V\N[v] . Since δ(G)≥ 2 and g≥ 5, then N(z)∩(V\N[v]) =∅ . Therefore, there exists w∈N(z) such that f(w) = 2 and f(N[z]) ≥ 3+|AN(z)|. Since G[V\V0]has no isolated vertices, then fis a t3RDF and γ[t3R](G)≤w(f) = 3+1+2(n−∆(G)−1) = 2(n−∆(G) + 1). As shown in Table 1, these bounds are not comparable. There are graphs for which each bound is better (boxed) than the others. Table 1. K− 4 stands for a complete graph K4 without an edge. Bound boxed is better than the others obtained bounds for the corresponding graph. Bounds C5P4◦K1K− 4 Proposition 210 16 8 Proposition 311 17 5 Proposition 48- - The upper bound can be significantly improved in the case of dealing with a regular graph, as demonstrated by the result we prove next. Proposition 5. Let G be an r -regular connected graph of order n and girth g≥ 7. Then, γ[t3R](G)≤2n−2r2+3r−1. Proof. Let v be any vertex of the graph G and let us denote N0={v} , N1=N(v) , and N2=N(N1)−N0 . Clearly, |N0|= 1, |N1|=r and |N2|=r(r− 1 ) because the girth is at least 7. Consider the function f:V→ { 0,1,2,3,4 } , defined as follows: f(v) = 1; f(z) = 3 for all z∈N1 ; f(z) = 0 for all z∈N2 ; and f(z) = 2 otherwise. Since r≥ 2 and the girth is greater than or equal to 7, we may readily verify that fis a t3RDF. Hence, γ[t3R](G)≤w(f) = 1+3r+2(n−1−r−r(r−1)) = 2n−2r2+3r−1. Although the upper bound matches the exact value, for example, of γ[t3R](C7) , it is worth pointing out that the girth condition is essential. It is not difficult to check Mathematics 2025,13, 1277 8 of 19 that γ[t3R](C5) = 8, whereas the upper bound given by Proposition 5would imply that γ[t3R](C5)≤7. In what follows, it is important to keep in mind certain conditions that, without loss of generality, we may assume that a γ[t3R](G)-function satisfies. Remark 1. Let f be a γ[t3R](G) -function of an ntc-graph G . Let v be a support vertex whose leaves are the vertices ui, with i ∈ {1, . . . , r}. Then, •If v is a weak support vertex, then f (u1)=4, f(v)=0, and f (u) + f(v) = 4. • If v is a strong support vertex such that f(wj) = 0for all wj∈N(v)\ {ui:i= 1, . . . , r} , then we may suppose that f (u1) = 1, f (v) = 4, and f (ui) = 0for all i =1. • If v is a strong support vertex such that there is a vertex wj0∈N(v)\ {ui:i= 1, . . . , r} with f (wj0)=0, then we may assume that f (v) = 4and f (ui) = 0for all the leaves ui. To close this section, we prove several results in which we bound the total triple Roman domination number of a graph in terms of other domination parameters such as the (total) domination number or the total double Roman domination number. Proposition 6. Let G be an ntc-graph; then, γ[t3R](G)≤5γ(G). Proof. Let D be a γ -set and D1⊆D the isolated vertices in the induced subgraph G[D] . For each v∈D1 , we consider a vertex ˜ v∈N(v) , and let us denote D2={˜ v:v∈D1} ⊆ V\D . Consider the function f:V→ { 0,1,2,3,4 } , defined as follows: f(z) = 4 for all z∈D ; f(z) = 1 for all z∈D2; and f(z) = 0 for the remaining vertices. Then, γ[t3R](G)≤4|D|+|D2| ≤ 4γ+|D1| ≤ 4γ+γ=5γ. (1) This bound is met by infinitely many graphs, such as those that contain a universal vertex. Corollary 1. Let G be an ntc-graph. If γ[t3R](G) = 5γ, then every γ-set is a 3-independent set. Proof. If γ[t3R](G) = 5 γ , then the inequalities in (1) become equalities. Therefore, |D1|=γ and all the dominating vertices are isolated in G[D] . Since |D2|=γ , there is no common neighbor ˜ v∈N(v)∩N(v′) for any pair v , v′∈D1 of distinct vertices. Consequently, every γ-set is a 3-independent set. We can readily check that the reciprocal is not always true by considering, for example, the cycle graph C9, for which γ[t3R](C9)≤14 <5γ(C9) = 15 (see Figure 4). 1 3 0 2 2 2 03 1 Figure 4. A total triple Roman dominating function on C9. Mathematics 2025,13, 1277 9 of 19 Proposition 7. Let G be an ntc-graph with at least 3vertices. Then, γt(G) + 3 ≤γ[t3R](G)≤ 4γt(G). Proof. Let S be a γt -set of G and let v∈S . We can readily prove the upper bound by considering a function g such that g(z) = 4 for all z∈S . This function g is a t3RDF and, hence, γ[t3R](G)≤4γt(G). Next, we prove the lower bound. Assume that f= (V0 , V1 , V2 , V3 , V4) is a γ[t3R](G) - function. Since V\V0is a total dominating set, we have that γt(G)≤ |V1|+|V2|+|V3|+|V4| =|V1|+2|V2|+3|V3|+4|V4|−|V2| − 2|V3| − 3|V4| =γ[t3R](G)− |V2| − 2|V3| − 3|V4|. If V4=∅ , then γt(G)≤γ[t3R](G)− 3 and we are finished. So, assume that V4=∅ . If V0=∅ , then either |V2| ≥ 3, {|V2| ≥ 1, |V3| ≥ 1 } , or |V3| ≥ 2 and, therefore, γt(G)≤ γ[t3R](G)− 3. So, the only case that remains to consider is V0=V4=∅ . But, in this situation, γt(G)≤n−1<n+2≤γ[t3R](G), which concludes the proof. Proposition 8. Let G be an ntc-graph. Then, γtdR(G)<γ[t3R](G)≤min5γ,3 2γtdR(G). Proof. First, to prove the lower bound, consider f= (V0 , V1 , V2 , V3 , V4) a γ[t3R](G) -function. If V4=∅ , then g= (V0 , V1 , V2 , V3∪V4) is a tdRDF with weight w(g)≤w(f)− 1 and, hence, γtdR(G)<γ[t3R](G). Assume now that V4=∅ , which implies that V2∪V3=∅ . Let v∈V2∪V3 be a vertex and consider the function g= (Vg 0 , Vg 1 , Vg 2 , Vg 3) , defined as follows: g(v) = f(v)− 1 and g(z) = f(z) otherwise. First, observe that the set V\V0 still total-dominates the graph G . On the other hand, the set of active neighbors of all vertices of V does not change regardless of which function, f or g , we consider. Therefore, if g(u)< 2 and u∈ N(v) , then g(N[u]) = f(N[u]) ≥ |AN(u)|+ 3 ≥ |AN(u)|+ 2. If g(u)< 2 and u∈N(v) , then g(N[u]) = f(N[u]) − 1 ≥ |AN(u)|+ 2. Hence, g is a tdRD function with a weight of w(g) = w(f)−1 and γtdR(G)<γ[t3R](G). To prove the upper bound, we consider g= (V0 , V1 , V2 , V3) a γtdR(G) -function. Let us define the following function: f(v) = 4 if v∈V3 ; f(v) = 3 if v∈V2 ; and g(z) = f(z) otherwise. Then, fis a t3RDF of Gand we may readily deduce that γ[t3R](G)≤f(V) = |V1|+3|V2|+4|V3| ≤ |V1|+3 2(2|V2|+3|V3|) ≤3 2(|V1|+2|V2|+3|V3|)=3 2γtdR(G). This fact, and the bound given by Proposition 6, lead us to the desired result. We conclude by providing two lower bounds in terms of the order, maximum degree, and domination number of the graph, some of which follow from well-known bounds for the triple Roman domination number. Proposition 9. Let G be an ntc-graph with n ≥3. Then, γ[t3R](G)≥γt(G) + γ(G). Mathematics 2025,13, 1277 16 of 19 To prove that γ[t3R](Pn)≥Mn for all n≥ 13, we reason by induction. Let n≥ 13 be an integer and assume that γ[t3R](Pm)≥Mm for all 2 ≤m<n . Let us denote V(Pn) = {uj: 1 ≤j≤n} such that the edges of the path are {ujuj+1} whenever j≤n− 1. So, we know that γ[t3R](Pn−8)≥Mn−8 and, by applying Lemma 3, we may derive that γ[t3R](Pn−5)≥ Mn−8+4. Analogously, it is deduced that γ[t3R](Pn−2)≥Mn−8+8=Mn−4. Let g be a γ[t3R](Pn) -function such that the number of vertices with a label 0 is the minimum. By Remark 1, we have that g(un) + g(un−1) = 4 and, without loss of generality, we may suppose that g(un) = 1, g(un−1) = 3. If g(V(Pn−2)) ≥Mn− 4, then we are finished because γ[t3R](Pn) = w(g) = g(V(Pn−2)) + 1+3≥Mn. Hence, assume that g(V(Pn−2)) <Mn− 4, which implies that g|Pn−2 is not a t3RDF in Pn−2 because Mn− 4 ≤Mn−2 . This may be due to several reasons, and we must study different situations. Case 1: g(un−2) = 0 . In this case, by Lemma 1, we have that g(un−3) = 2 and g(un−4) = 2. If g(un−5) = 1, then we have to study two different possibilities: either g(un−6) = 2 and g(un−7)≥2 or g(un−6) = 3 and g(un−7)≥0 . In both cases, we may define the following function: g′(un−5) = 0, g′(un−6) = 3, g′(un−7) = 1, g′(un−8) = min{ 3, g(un−8) + g(un−5) + g(un−6) + g(un−7)− 4 } , and g′(z) = g(z) otherwise. The function g′ is a t3RDF with the same weight as g . We can proceed similarly if g(un−5) = 2 or g(un−5) = 3. Therefore, we may assume that g(un) = 1, g(un−1) = 3, g(un−2) = 0, g(un−3) = 2, g(un−4) = 2, g(un−5) = 0, g(un−6) = 3, and g(un−7) = 1. Since V4=∅, then g(un−8)≥1. Case 1.1: 1≤g(un−8)≤2 .Then, g(un−9)≥ 2 and g(un−8) + g(un−9)≥ 4. Thus, g|Pn−8 is a t3RDF in Pn−8 and, consequently, g(V(Pn−8)) ≥γ[t3R](Pn−8)≥Mn−8 , implying that γ[t3R](Pn) = w(g)≥Mn−8+12 =Mn. Case 1.2: g(un−8) = 3 .Then, we may define the following function: g′(un−8) = 1, g′(un−9) = min{ 3, g(un−9) + 2 } , and g′(z) = g(z) otherwise. The function g′ is a t3RDF under the conditions of Case 1.1. Case 2: g(un−2)=0 , g(un−3) = 0 . In this case, we may define the function g′(un−2) = 0, g′(un−3) = g(un−2) , and g′(z) = g(z) otherwise, which is a t3RDF under the conditions of Case 1. Case 3: g(un−2) = 1, g(un−3)=0 . Clearly, g(un−3)≤ 2, because g|Pn−2 is not a t3RDF in Pn−2 . g(un−3) + g(un−4)≥ 4, and we have that g|Pn−3 is a t3RDF in Pn−3 , and so γ[t3R](Pn) = w(g) = g(V(Pn−3)) + g(un−2) + g(un−1) + g(un)≥Mn−3+5≥Mn. Case 4: g(un−2)≥2, g(un−3)=0 . We can define the function g′(un−2) = 1, g′(un−3) = min{ 3, g(un−3) + g(un−2)− 1 } and g′(z) = g(z) otherwise, which is a t3RDF under the conditions of Case 3. Summarizing, we have shown that γ[t3R](Pn)≥Mn, which concludes the proof. Theorem 2. Let be n ≥3a positive integer. Then, γ[t3R](Cn) =    ⌈3n 2⌉if n ≡0,1, 3,5,7 (mod 8). ⌈3n 2⌉+1if n ≡2,4, 6 (mod 8). Proof. Let us denote Mn=   ⌈3n 2⌉if n≡0,1,3,5,7 (mod 8). ⌈3n 2⌉+1 if n≡2,4,6 (mod 8). Mathematics 2025,13, 1277 17 of 19 Note that Mn=Mnwhenever n=4, 7 and Mn=Mn−1 for n∈ {4,7}. First, as shown in Figure 5, we have that γ[t3R](Cn)≤Mn for n∈ { 4,7 } . On the other side, since γ[t3R](Cn)≤γ[t3R](Pn) , then we also have that γ[t3R](Cn)≤γ[t3R](Pn) = Mn= Mnfor all n=4, 7. 2 2 3 0 3 1 3 0 2 0 2 Figure 5. Total triple Roman dominating functions for C4and C7. To prove the other inequality, we proceed by induction on the order of the cycle. By Proposition 13, we have that γ[t3R](Cn)≥6n 5+2=Mnfor n≤8. Let n≥ 9 be an integer, and assume that γ[t3R](Cn′)≥Mn′ for all 3 ≤n′<n . Denote by V(Cn) = {u1 , . . . , un} the set of consecutive vertices of the cycle. Let f be a γ[t3R](Cn) -function such that the number of vertices labeled with 0 is the minimum, which, by applying Lemma 1, implies that V4=∅ . Since n≥ 9, we may consider five consecutive vertices, say {ui−2 , ui−1 , ui , ui+1 , ui+2} . By Proposition 2, we can assume that g(ui) = 0 and, again by Lemma 1, we may suppose, without loss of generality, that f(ui−2) = f(ui−1) = 2, f(ui+1) = 3, f(ui+2) = 1 and f(ui+3)= 0. We have to discuss some different possibilities. Case 1: f(ui−3) = 0 . In this case, it must be that f(ui−4) = 3, f(ui−5) = 1 and f(ui−6)= 0. Case 1.1: f(ui−6) + f(ui+3)≥4 . We can readily check that γ[t3R](Cn)≥Mn for n= 9,10. Let n≥ 11 and consider the cycle C′ or order n− 8 obtained by joining ui−6 and ui+3 . Thus, f|C′ is a t3RDF and γ[t3R](Cn) = f(V(Cn)) = f(V(C′)) + f(ui−5) + f(ui−4) + f(ui−3) + f(ui−2) + f(ui−1) + f(ui) + f(ui+1) + f(ui+2)≥M(n−8) + 12 ≥Mn. Case 1.2: f(ui−6) = f(ui+3) = 1 . Then, it must be that f(ui−7) = f(ui+4) = 3, and the cycle C′ or order n− 8 obtained by joining ui−6 and ui+3 satisfies that f|C′ is a t3RDF with γ[t3R](Cn) = f(V(Cn)) = f(V(C′)) + f(ui−5) + f(ui−4) + f(ui−3) + f(ui−2) + f(ui−1) + f(ui) + f(ui+1) + f(ui+2)≥M(n−8) + 12 ≥Mn. Case 1.3: f(ui−6) = 2, f(ui+3) = 1 , which implies that f(ui+4) = 3 and f(ui−7)≥ 2. If i+ 4 =i− 7, then n= 11 and γ[t3R](C11) = w(f) = 18 ≥ 17 =M11 . Thus, assume that n≥ 12. If ui+4 is adjacent to ui−7 , then n= 12 and γ[t3R](C12) = w(f)≥ 20 ≥ 19 =M12 . Thus, assume that n≥ 13 and consider the cycle C′ or order n− 8 obtained by joining ui−6 and ui+3 . Again, f|C′ is a t3RDF with γ[t3R](Cn) = f(V(Cn)) = f(V(C′)) + f(ui−5) + f(ui−4) + f(ui−3) + f(ui−2) + f(ui−1) + f(ui) + f(ui+1) + f(ui+2)≥M(n− 8 ) + 12 ≥ Mn. Case 2: f(ui−3) = 1 . Then, it must be that f(ui−4)≥ 2. Let C′ be the cycle or order n− 1 obtained by joining ui−4 and ui−2 . We have that γ[t3R](Cn) = f(V(Cn)) = f(V(C′)) + f(ui−3)≥M(n−1) + 2≥Mn. Case 3: f(ui−3)≥2 . If so, we may consider the cycle C′ or order n− 1 obtained by joining ui−3 and ui−1 . We can readily check that f|C′ is a t3RDF and γ[t3R](Cn) = f(V(Cn)) = f(V(C′)) + f(ui−2)≥M(n−1) + 2≥Mn. Mathematics 2025,13, 1277 18 of 19 This concludes the proof. In this section, we characterized those graphs with the minimum possible value of γ[t3R](G) = 5 and proved that there are no graphs with γ[t3R](G) = 6. We also determined the exact values of the total triple Roman domination number γ[t3R] for paths and cycles. For paths Pn of order n≥ 3, we established that γ[t3R](Pn) = Mn , where Mn is defined based on modular arithmetic conditions (Theorem 1). For cycles Cn , we showed that γ[t3R](Cn) = ⌈3n 2⌉ when n≡ 0,1,3, 5,7 (mod 8 ) and γ[t3R](Cn) = ⌈3n 2⌉+ 1 when n≡ 2,4,6 (mod 8 ) (Theorem 2). These results highlight the structural differences between paths and cycles and provide a foundation for further exploration of this parameter in other graph families. 6. Discussion In this paper, we introduced a novel concept called total triple Roman domination in graphs, which represents a variant of the classical Roman domination problem by requiring additional conditions on dominating sets to provide greater robustness and reliability for a graph. The new concept was formally defined, and it was shown that the associated decision problem is NP-complete even when restricted to bipartite graphs. Moreover, several sharp upper and lower bounds for the parameter were obtained, as well as the exact value for some particular graphs. The total triple Roman domination model has potential uses in real-world scenarios requiring layered defense mechanisms, such as the below. • Cybersecurity networks, where nodes with higher labels represent multi-layered firewalls. • Urban planning, ensuring backup resources (e.g., hospitals, police stations) are optimally placed. • Robust sensor coverage in IoT systems, minimizing blind spots. As a future line of research, we intend to prove that the problem remains NP-complete in general but can be reduced to a linear problem in specific families of graphs, such as trees. Additionally, the exact value of the parameter should be investigated for other graphs or graph families with specific structural properties. Author Contributions: Conceptualization, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; methodology, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; validation, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; investigation, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R.; writing—review and editing, J.C.V.-T., M.A.M.-C., M.C. and M.P.A.-R. All authors have read and agreed to the published version of the manuscript. Funding: J.C. Valenzuela-Tripodoro was partially supported by the Spanish Ministry of Science and Innovation through the grant PID2022-139543OB-C41. Data Availability Statement: No new data were created. Conflicts of Interest: The authors declare no conflicts of interest. References 1. Arquilla, J.; Fredricksen, H. Graphing an Optimal Grand Strategy. Mil. Oper. Res..1995,1, 3–17. [CrossRef] 2. ReVelle, C.S. Can you protect the Roman Empire. Johns Hopkins Mag. 1997,49, 40. 3. ReVelle, C.S.; Rosing, K.E. Defendens imperium romanum: A classical problem in military strategy. Am. Math. Mon. 2000,107, 585–594. [CrossRef] 4. Stewart, I. Defend the Roman Empire! Sci. Am. 1999,281, 136–139. [CrossRef] 5. Cockayne, E.J.; Dreyer, P.A.; Hedetniemi, S.M.; Hedetniemi, S.T. Roman domination in graphs. Discret. Math. 2004,278, 11–22. [CrossRef] 6. Chellali, M.; Haynes, T.W.; Hedetniemi, S.T. Bounds on weak roman and 2-rainbow domination numbers. Discret. Appl. Math.. 2014,178, 27–32. [CrossRef] Mathematics 2025,13, 1277 19 of 19 7. Cockayne, E.J.; Favaron, O.; Mynhardt, C.M. Secure domination, weak Roman domination and forbidden subgraphs. Bull. Inst. Comb. Its Appl. 2003,39, 87–100. 8. Klostermeyer, W.F.; Mynhardt, C.M. Secure domination and secure total domination in graphs. Discuss. Math. Graph Theory.2008, 28, 267–284. [CrossRef] 9. Valveny, M.; Pérez-Rosés, H.; Rodríguez-Velázquez, J.A. On the weak Roman domination number of lexicographic product graphs. Discret. Appl. Math. 2019,263, 257–270. [CrossRef] 10. Valveny, M.; Rodríguez-Velázquez, J.A. Protection of graphs with emphasis on cartesian product graphs. Filomat 2019,33, 319–333. [CrossRef] 11. Liu, C.H.; Chang, G.J. Roman domination on strongly chordal graphs. J. Comb. Optim. 2013,26, 608–619. [CrossRef] 12. Beeler, R.A.; Haynes, T.W.; Hedetniemi, S.T. Double Roman domination. Discret. Appl. Math. 2016,211, 23–29. [CrossRef] 13. Shao, Z.; Amjadi, J.; Sheikholeslami, S.M.; Valinavaz, M. On the Total Double Roman Domination. IEEE Access 2019,7, 52035–52041. [CrossRef] 14. Hao, G.; Volkmann, L.; Mojdeh, D.A. Total double Roman domination in graphs. Commun. Comb. Optim. 2020,5, 27–39. [CrossRef] 15. Abdollahzadeh Ahangar, H.; Álvarez Ruiz, M.P.; Chellali, M.; Sheikholeslami, S.M.; Valenzuela-Tripodoro, J.C. Triple Roman domination in graphs. Appl. Math. Comput. 2021,391, 125444. [CrossRef] 16. Hajjari, M.; Abdollahzadeh Ahangar, H.; Khoeilar, R.; Shao, Z.; Sheikholeslami, S.M. An upper bound on triple Roman domination. Commun. Comb. Optim. 2023,8, 505–511. [CrossRef] 17. Valenzuela-Tripodoro, J.C.; Mateos-Camacho, M.A.; Cera, M.; Álvarez-Ruiz, M.P. Further results on the [k]-Roman domination in Graphs. Bull. Iran. Math. Soc. 2024,50, 27. [CrossRef] Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.