Proposition 1 (see [12].)In a double Roman dominating function of weight γ_dR(G), no vertex needs to be assigned the value 1.

Proposition 2 (see [12].) 

• (i)

  Let G be a graph and f = (V₀, V₁, V₂) be a γ_R(G) function. Then, γ_dR(G) ≤ 2|V₁| + 3|V₂|.

• (ii)

  For any graph G, γ_dR(G) ≤ 2γ_R(G) with equality if and only if $$.

Proposition 3 (see [12].) 

• (i)

  For every graph G, γ_R(G) < γ_dR(G).

• (ii)

  If f = (V₀, ∅, V₂, V₃) is any γ_dR(G) function, then γ_R(G) ≤ 2(|V₂| + |V₃|) = γ_dR(G) − |V₃|.

Proposition 4. For any graph G, γ_dR(G) ≥ (3|V(G)|/Δ(G) + 1).

Proof. The desired inequality obviously holds if Δ(G) ≤ 1. In order to prove the proposition for Δ(G) ≥ 2, we introduce the discharging approach. Let f = (V₀, ∅, V₂, V₃) be a γ_dR(G) function. The initial charge of every vertex v ∈ V(G) is set to be s(v) = f(v). We apply the discharging procedure defined by applying the following rule.

For each vertex v ∈ V₃, we send 3/(d(v) + 1) charge to each adjacent vertex in V₀. Then, the final charge of v is satisfying with s(v) = (3/(d(v) + 1)) ≥ (3/(Δ(G) + 1)).

For each vertex v ∈ V₂, we send (2/(d(v) + 1)) − (3/(d(v)(Δ(G) + 1))) = ((2Δ(G) − 1)/(d(v)(Δ(G) + 1))) ≥ ((2Δ(G) − 1)/(Δ(G)(Δ(G) + 1))) charge to each adjacent vertex in V₀. Then, the final charge of v is satisfying with s(v) = (3/(d(v) + 1)) ≥ (3/(Δ(G) + 1)).

For each vertex v ∈ V₀, by the definition of double Roman domination, v has a neighbor assigned 3 or two vertices u₁ and u₂ assigned 2. Due to the discharging rule above, if v has a neighbor u assigned 3, v receives charge from u. We have s(v) ≥ (3/(Δ(G) + 1)).

If v has two vertices u₁ and u₂ assigned 2, v receives charge from u₁ and u₂. We have s(v) ≥ ((4Δ(G) − 2)/(Δ(G)(Δ(G) + 1))) ≥ (3/(Δ(G) + 1)). Thus, γ_dR(G) = ∑_v∈V(G)f(v) = ∑_v∈V(G)s(v) ≥ ((3|V(G)|)/(Δ(G) + 1)). The proof is complete.

Proposition 5. Let G be a graph. If γ_R(G) + 1 = γ_dR(G) and f = (V₀, ∅, V₂, V₃) is a γ_dR(G) function,

• (i)

  then  |V₃| ≤ 1

• (ii)

  if |V₃| = 1, then |V₂| = 0 and there exists a vertex v with degree |V(G)| − 1.

Proof.  

• (i)

  By Proposition 3, we have γ_R(G) ≤ γ_dR(G) − |V₃| = γ_R(G) + 1 − |V₃|. So we have |V₃| ≤ 1.

• (ii)

  If |V₃| = 1, let V₃ = {v} and H = G[V(G) − N[V₃]]. We have the following claim.

Claim 1. H is empty.

Proof. Otherwise, any vertex in H assigned with 0 has at least two vertices assigned with 2. Let w be a vertex in H assigned with 2, we consider a function f^′ with f^′(w) = 1, f^′(v) = 2, and f^′(x) = f(x) for any x ∈ V(G) − {v, w}. Then, f^′ is an RDF of G with weight γ_dR(G) − 2. So γ_R(G) ≤ γ_dR(G) − 2, a contradiction.

Since H is empty, we have v as a vertex with degree |V(G)| − 1. Now, we have γ_dR(G) = 3 and γ_R(G) = 2, and so the result holds.

Theorem 1. For every graph G on n vertices without isolated vertex, γ_dR(G) ≤ 3n − (3n/(2(1 + δ(G))))e^1/δ(G).

Proof. Clearly, we have δ(G) ≥ 1. We select a subset S of V(G), where each vertex is selected with probability p independently. Let T = V(G) − N[S], we consider a function f : V(G)⟶{0,2,3} with f(x) = 3 for x ∈ S, f(x) = 2 for x ∈ T, and f(x) = 0 for other vertex x. Then, f is a DRDF of G. We have γ_dR(G) ≤ 3|S| + 2|T|. When we consider the expectation, we also have γ_dR(G) ≤ E[3|S| + 2|T|] = 3E[|S|] + 2E[|T|]. First, it is clear that E[|S|] = np. For each vertex with degree d(x), if neither x nor any neighbor is selected, then x ∈ T. So we have P(x ∈ T) = (1 − p)^1+d(x), and thus, E[|T|] ≤ n(1 − p)^1+δ(G). Consequently, γ_dR(G) ≤ 3np + 2n(1 − p)^1+δ(G). Let F(p) = 3np + 2n(1 − p)^1+δ(G). By F(p) = 3np − 2n(1 + δ(G))(1 − p)^δ(G) = 0, the maximum of F is given by F_max = 3n − (3n/(2(1 + δ(G))))e^1/δ(G) at p = 1 − (3/(2(1 + δ(G))))e^1/δ(G) ∈ (0,1). Thus, γ_dR(G) ≤ 3n − (3n/(2(1 + δ(G))))e^1/δ(G).

If G is a graph with some isolated vertices, then δ(G) = 0. Let W be the set of isolated vertices of G and let G^′ = G − W. Therefore, δ(G^′) ≥ 1. Because all isolated vertices must be assigned 3, it is easy to prove that $$, where n^′ = |V(G^′)|.

Proposition 6. If G is a connected graph of order n, then γ_dR(G) + 1 = 2γ_R(G) if and only if there exists a vertex v of degree n + 1 − ((γ_dR(G) + 1)/2) in G.

Proof.  

•  

  (⇒) Let f = (V₀, V₁, V₂) be a γ_R(G) function with minimum |V₁|. Then, we have V₁ being independent. Together with Proposition 2, we have γ_dR(G) ≤ 2|V₁| + 3|V₂| ≤ 2|V₁| + 4|V₂| = 2γ_R(G) = γ_dR(G) + 1. Then, we have |V₂| ≤ 1. If |V₂| = 0, we have |V₀| = 0, and thus γ_R(G) = n = |V₁|. Since V₁ is independent, it is impossible. If |V₂| = 1, we have γ_dR(G) = 2|V₁| + 3|V₂| < 2|V₁| + 4|V₂| = 2γ_R(G) = γ_dR(G) + 1. Let V₂ = {v}, V₀ = N(v), and V₁ = V(G) − V₀ − V₂. Then, we have γ_R(G) = n − 1 − d(v) + 2 and so d(v) = n + 1 − γ_R(G) = n + 1 − ((γ_dR(G) + 1)/2).

•  

  (⇐) By Proposition 2 (ii), we have γ_dR(G) + 1 ≤ 2γ_R(G) for a connected graph G. Assume G contains a vertex v of degree n + 1 − (γ_dR(G) + 1)/2 in G. Let V₂ = {v}, V₀ = N(v), and V₁ = V(G) − V₀ − V₂. Then, f = (V₀, V₁, V₂) is a γ_R(G) function and so γ_R(G) ≤ |V₁| + 2|V₂| = (γ_dR(G) + 1)/2. Hence, γ_dR(G) + 1 ≥ 2γ_R(G).

Let ℱ be the family of connected graphs G such that for any γ_dR(G) function f = (V₀, ∅, V₂, V₃), we have |V₃| = 0.

Proposition 7. Let G ∈ ℱ, then

• (i)

  G contains no strong support vertex

• (ii)

  if f(u) = f(v) = 2 for an edge uv ∈ E(G), then G − e ∈ ℱ and G/e ∈ ℱ.

Proof.  

• (i)

  Suppose v be a strong support vertex, then there exist two leaves x, y ∈ N(v). Since f(v) ≠ 3, we have f(x) = f(y) = 2. Now consider the function f^′ with f^′(z) = 0 for any z ∈ L(v), f^′(v) = 3, and f^′(z) = f(z) for any z ∈ V(G)∖L[v]. Then, f^′ is a DRDF of G with fewer weight than f, a contradiction.

• (ii)

  If f(u) = f(v) = 2 for an edge uv ∈ E(G), we have f as also a DRDF of G − e. So γ_dR(G − e) ≤ w(f) = γ_dr(G). Since for any graph G, we have γ_dR(G − e) ≥ γ_dR(G), so γ_dR(G − e) = γ_dR(G). Suppose to the contrary that there exists a γ_dR(G − e) function such that f(v) = 3 for a vertex v ∈ V(G − e). Then, f is also a γ_dR(G) function, contradicting with |V₃| = 0. For the graph G/e, the proof is similar.

Lemma 1. Let G be a graph on n ≥ 4 vertices, then γ_dR(G) = 4 if and only if G contains a complete bipartite graph K_2,n−2 as a subgraph and Δ(G) ≤ n − 2.

Proof.  

•  

  (⇒) If γ_dR(G) = 4, then no vertex is assigned with 3 and thus we have two vertices v and w assigned with 2 and the others 0. Also, each vertex 0 must be adjacent to both v and w. Therefore, G contains a complete bipartite graph K_2,n−2 as a subgraph. Since γ_dR(G) > 3, we have Δ(G) ≤ n − 2.

•  

  (⇐) If G contains a complete bipartite graph K_2,n−2 with partitions X, Y (|X| = 2, |Y| = n − 2) as a subgraph and Δ(G) ≤ n − 2. Then, let f(x) = 2 for any x ∈ X and f(x) = 0 for x ∈ Y. Then, f is a DRDF of G and so γ_dR(G) ≤ 4. Since G contains no vertex with degree |V(G)| − 1, we have γ_dR(G) ≥ 4.

Note that Δ(G) ≥ n − 2 if G contains a complete bipartite graph K_2,n−2 as a subgraph. Thus, Δ(G) ≤ n − 2 can be replaced with Δ(G) = n − 2 in the lemma.

Theorem 2. Let G be a graph on n ≥ 3 vertices, then $$. Furthermore, equality holds in the upper bound if G or $$ is K_n.

Proof. If G is a graph on n ≥ 3 vertices, we have γ_dR(G) ≥ 3, and if γ_dR(G) = 3, then G has a vertex with degree n − 1. But its complement is neither a star nor a graph G with γ_dR(G) = 4 (see the graph stated in Lemma 1). So we have $$ and thus, $$. If G is a star, then $$ and so the lower bound is attainable.

Let v be a vertex with maximum degree Δ(G); consider a function f with f(v) = 3, f(x) = 0 for any x ∈ N(v), and f(x) = 2 for x ∈ V(G) − N[x]. Then, f is a DRDF of G and so γ_dR(G) ≤ w(f) = 2n − 2Δ(G) + 1. Since $$, we have $$. Therefore, $$. It can be seen that if $$, then Δ(G) = δ(G). Hence, G is k-regular for some k. By symmetry, we may assume that k ≤ (n − 1)/2. Then, if $$, we have γ_dR(G) = 2n − 2k + 1 and $$. Let v ∈ V(G). If |N(u)∩N(v)| ≤ k − 2 for some u ∈ V(G) − N[v], then f = (N(v) ∪ N(u), ∅, V(G) − N[u] − N[v], {u, v}) is a DRDF of G with fewer weight than 2n − 2k + 1, a contradiction. Therefore, each vertex not in N[v] has at least k − 1 neighbors in N(v). Analogously, each vertex in N[v] has at most 2 neighbors outside N[v]. Then, we have (k − 1)(n − k − 1) ≤ 2k. Since k ≤ (n − 1)/2, we have k ≤ 2 + 2/(k − 1). If k = 3, then n = 7. This is impossible. If k = 2, then n ∈ {5,6,7}. If G = C₅, we have $$, and so $$, a contradiction. If G = C₆, we have $$, and so $$, a contradiction. If G = C₇, we have $$, and so $$, a contradiction. If k = 1, then G = (n/2)K₂, and we have γ_dR(G) = 3n/2 and $$, and so $$, a contradiction. Therefore, we conclude that $$. If G = K_n, then $$ and thus the upper bound is attainable.

Theorem 3. Let m, n ≥ 1. Then, the Cartesian product graphs C_5m□C_5n are double Roman.

Proof. The lower bound follows from Proposition 4. Let V(C_5m□C_5n) = {v_ij : 0 ≤ i ≤ 5m − 1,0 ≤ j ≤ 5n − 1}, V₁ = V₂ = ∅, V₃ = {v_{(5i)(5j + 2)}, v_{(5i + 1)(5j)}, v_{(5i + 2)(5j + 3)}, v_{(5i + 3)(5j + 1)}, v_{(5i + 4)(5j + 4)}, 0 ≤ i ≤ m − 1, 0 ≤ j ≤ n − 1}, and V₀ = N(V₃). Then, N[V₃] = V(C_5m□C_5n) and so f = (V₀, V₁, V₂, V₃) is a DRDF of C_5m□C_5n with weight 15mn and we have γ_dR(C_5m□C_5n) ≤ 15mn. Since γ(C_5m□C_5n) = 5mn, we have C_5m□C_5n is double Roman.

Theorem 4. If T is a tree, then γ_R(T) + 1 = γ_dR(T) if and only if T is a star K_1,s for s ≥ 1.

Proof.  

•  

  (⇐) If T is a star K_1,s for s ≥ 1, it is clear that γ_dR(T) = 3 and γ_R(T) = 2, and the theorem holds.

•  

  (⇒) By Proposition 3, we have |V₃| ≤ 1. If |V₃| = 1, by Proposition 5, we have T is a star K_1,s for some s ≥ 1. If |V₂| = 0, then each vertex in T is assigned 2 or 0. Since T is a tree, T has a least two leaves v and w and f(v) = f(w) = 2. If v and w are adjacent to the same vertex x, then we can obtain a DRDF of T with fewer weight by changing f(x) to 3 and f(v) and f(w) to 0 and obtaining a contradiction. If v and w are adjacent to different vertices, we consider a function f^′ with f^′(w) = 1, f^′(v) = 1, and f^′(x) = f(x) for any x ∈ V(T) − {v, w}. Then, f^′ is an RDF of T with weight γ_dR(T) − 2. So γ_R(T) ≤ γ_dR(T) − 2, a contradiction.

For a positive integer t, a wounded spider is a star K_1,t with at most t − 1 of its edges subdivided. In a wounded spider, a vertex of degree t will be called the head vertex, and the vertices at distance two from the head vertex will be the foot vertices.

Theorem 5. If T is a tree, then γ_R(T) + 2 = γ_dR(T) if and only if T is a wounded spider with only one foot or T is obtained by adding an edge between two stars K_1,s and K_1,t for s, t ≥ 2.

Proof.  

•  

  (⇐) If T is a wounded spider with only one foot, it is clear that γ_dR(T) = 5 and γ_R(T) = 3, and the theorem holds. If T is a tree obtained by adding an edge between two stars K_1,s and K_1,t for s, t ≥ 2, then γ_dR(T) = 6 and γ_R(T) = 4, and the theorem holds.

•  

  (⇒) By Proposition 3, we have |V₃| ≤ 2. If |V₃| = 2, let V₃ = {v, w} and H = G[V(G) − N[w] − N[v]]. Similar to the proof of Theorem 5, we have H as empty. Otherwise, there exists a vertex u in H assigned with 2. Now, we change the function values of v, w, u from 3,3,2 to 2,2,1, respectively, and obtain an RDF of T with weight γ_dR(T) − 3, a contradiction. In this case, T is a tree obtained by adding an edge between two stars K_1,s and K_1,t for s, t ≥ 2. If |V₃| = 1, let V₃ = {v} and H = G[V(G) − N[v]]. Then, H has at most one connected component. Otherwise, we can make a vertex in each connected component to change the function values including the vertex v to obtain an RDF of T with weight γ_dR(T) − 3. Since H contains no vertex assigned with 3, then H is not a star with at least two leaves. We claim that the leaves of H are at most two. Otherwise, we change the function values of v and choose two leaves to obtain an RDF of T with weight γ_dR(T) − 3. Therefore, H is a path on at least four vertices. In this case, we can obtain an RDF of T with weight at most γ_dR(T) − 3, a contradiction. Therefore, T is a wounded spider with only one foot.