Impact of Some Graph Operations on Double Roman Domination Number

Anu V.; Aparna Lakshmanan S.

REVIEW 6 major objections 4 minor 12 references

Impact of Some Graph Operations on Double Roman Domination Number

T0 review · 6 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper determines the double Roman domination number exactly for $2\times n$ grids and for corona products, and bounds it under Cartesian products and twin additions.

desk verdict New formulas for a natural variant of Roman domination, but two central proofs do not hold as written: the exact grid value and the corona realization are unsupported. read the letter →

arxiv 1908.06859 v1 pith:YPBT2POQ submitted 2019-08-19 math.CO

Anu V. , Aparna Lakshmanan S. This is my paper · ORCID

classification math.CO MSC 05C6905C76

keywords doubleRomandominationnumberCartesianproductgridgraphcoronatrueandfalsetwinsrealizabilityofparameters

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Double Roman domination is a graph-protection cost model: each vertex receives 0, 2, or 3, a vertex receiving 0 must see either two neighbors receiving 2 or one neighbor receiving 3, and in a minimum solution no vertex need receive 1. The paper works out how the minimum total weight behaves when graphs are combined by Cartesian products, corona products (attaching a copy of one graph to each vertex of another), and twin additions. It gives the exact value for the $2\times n$ grid as $\lfloor(3n+4)/2\rfloor$, and shows that the corona $G\odot H$ with any nontrivial $H$ costs exactly $3|V(G)|$, while $G\odot K_1$ costs between $2|V(G)|+1$ and $3|V(G)|$, with every integer in that interval realized. For Cartesian products it proves $\gamma_{dR}(G\square H)>\gamma(G)\gamma_{dR}(H)/2$ together with an upper bound in terms of the order of either factor. It also rules out the pair $(\gamma_R,\gamma_{dR})=(a,a+1)$ for even $a>2$ and realizes a broad range of other pairs on connected bipartite graphs.

What carries the argument

The carrying object is the double Roman dominating function (DRDF), a map $f:V\to\{0,2,3\}$ whose weight $f(V)$ is minimized, together with the fact that a minimum DRDF need never use the value 1. For Cartesian products the main mechanism is a slice-and-project argument: take a minimum dominating set of one factor, partition that factor into closed-neighborhood pieces, slice the product over those pieces, push the inherited assignment down to the other factor, and compare weights; binary vectors record which slices fail, and a domination argument on the other factor bounds their total. For the grid, the upper bound comes from an explicit periodic placement of 3s with one 2 on the end for even $n$, while the lower-bound argument assigns weight to the members of a minimum dominating set and uses the closed neighborhoods around them. For coronas and twins, the machinery is local forcing: pendant vertices must be protected from outside their own edge, and twin vertices can be handled by restricting or re-assigning a minimum function.

What would settle it

Enumerate all $3^6$ assignments $V\to\{0,2,3\}$ on the $2\times3$ grid and check the two double Roman conditions: the formula predicts $\gamma_{dR}=6$, so an assignment of weight 5 would refute Theorem 2.5, while confirming 6 would leave the formula intact for that case but still show the partition assertion used in the proof is false.

Watch

Extended reading notes

Core claim

The central claim is that several common graph operations change the double Roman domination number in a controlled, mostly computable way. On the $2\times n$ grid $G_{2,n}$ with $n\neq2$, the paper asserts $\gamma_{dR}(G_{2,n})=\lfloor(3n+4)/2\rfloor$, achieved by a periodic pattern of 3s and, for even $n$, a single 2 at the far end. For the corona $G\odot H$ with $H\not\cong K_1$, it claims $\gamma_{dR}=3|V(G)|$; for $G\odot K_1$, the value lies in the interval $[2|V(G)|+1,\,3|V(G)|]$ and every integer in that interval occurs. For a Cartesian product, the paper proves $\gamma_{dR}(G\square H)>\gamma(G)\gamma_{dR}(H)/2$ and $\gamma_{dR}(G\square H)\le\min\{|V(H)|\gamma_{dR}(G),|V(G)|\gamma_{dR}(H)\}$. Adding a true twin raises the number by at most 1, and a false twin by at most 2, and neither addition can lower it. Finally, no graph realizes $(\gamma_R,\gamma_{dR})=(a,a+1)$ when $a>2$ is even, whereas every pair $(a,b)$ with $a=\lfloor b/2\rfloor+1,\ldots,2\lfloor b/2\rfloor-1$ is realized by some connected bipartite graph.

Load-bearing premise

The load-bearing premise is that in the lower-bound proof for the $2\times n$ grid, the closed neighborhoods $N[x_i]$ of a dominating set $\{x_1,\ldots,x_\gamma\}$ partition the vertex set; this is false for $n=3$ with the dominating set $\{a_2,b_2\}$, whose closed neighborhoods overlap, so the proof of Theorem 2.5 is not supported as written.

Editorial extensions

If this is right

For any graph $G$ and any nontrivial $H$, the corona $G\odot H$ has $\gamma_{dR}=3|V(G)|$, so the double Roman number of such a corona is determined entirely by the size of the base graph.
For $G\odot K_1$, the parameter can be tuned to every integer between $2|V(G)|+1$ and $3|V(G)|$, and for paths and cycles the paper gives explicit values asymptotic to $7n/3$.
The product inequalities place $\gamma_{dR}(G\square H)$ strictly above $\gamma(G)\gamma_{dR}(H)/2$ and at most $\min\{|V(H)|\gamma_{dR}(G),|V(G)|\gamma_{dR}(H)\}$, so both factors constrain the product's cost.
Adding a true twin increases the double Roman number by at most 1 and adding a false twin by at most 2, and neither operation ever lowers it.
The realizability results show which pairs $(\gamma_R,\gamma_{dR})$ coexist, excluding $(a,a+1)$ for even $a>2$ while covering every value between $\lfloor b/2\rfloor+1$ and $2\lfloor b/2\rfloor-1$ on connected bipartite graphs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The periodic 3/2 construction in the grid theorem gives a ready upper bound for $2\times n$ grids; if a correct lower-bound argument replaces the closed-neighborhood partition step, the same pattern is a natural starting point for exact values on wider $m\times n$ grids.
The slice-and-project argument suggests a Vizing-type product inequality: $\gamma_{dR}(G\square H)$ should be bounded below by a constant factor of $\gamma(G)\gamma_{dR}(H)$, and similar ratio bounds may hold for total Roman and other Roman-type parameters.
The constructions that tune $G\odot K_1$ and the bipartite realization graphs give a way to force $\gamma_{dR}$ to any prescribed value in an interval while keeping the graph structurally simple, which may serve as a building block for hardness or approximation results.
The exclusion of $(a,a+1)$ for even $a>2$ leaves open which pairs close to $\gamma_{dR}=2\gamma_R$ are realizable; the paper's range covers most of the interval, and the remaining gap is a concrete finite search problem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here is my read of arXiv:1908.06859. The paper extends the double Roman domination program to Cartesian products, coronas, and twin addition. The questions are natural, and the paper catalogs plausible exact values: gamma_dR(G_{2,n}) = floor((3n+4)/2) for n != 2, gamma_dR(G ⊙ H) = 3n for H not K1, bounds for G ⊙ K1, and twin-addition bounds. Some of these are genuinely new relative to the cited literature, and the easy upper-bound constructions are clean. Proposition 3.1, Theorem 2.4, and the general twin bounds are fine in spirit.

The soft spots are load-bearing. Theorem 2.5's lower bound asserts that for odd n the closed neighborhoods of an arbitrary dominating set partition the vertex set of G_{2,n}. That is false: for n = 3, the two middle vertices form a dominating set whose closed neighborhoods overlap. The even case's partition with at most one singleton block is also asserted without proof. The claimed equality therefore rests on an invalid partition argument; the upper bound alone does not establish the result.

Proposition 3.3's converse construction also fails. In the corona of K_{1,m} ∪ (n-m-1)K_1 with K_1, the leaf u'_j for j = 2,...,m+1 is assigned 0 while its support u_j gets 2. A zero vertex needs two neighbors in V2 or one in V3; that leaf has exactly one neighbor total, so the condition fails. The weight calculation is correct, but it computes the weight of a function that is not a DRDF.

There are smaller gaps too. Theorem 4.1's left-inequality proof sketches cases without fully justifying why a gamma_dR-function on H restricts to one on G; the true-twin case needs a minimality argument that is only gestured at. Theorem 5.2's "easy to verify that these functions are in fact minimum" is a promise, not a proof.

The core issue is not the topic or the results — the formulas may well be true. But as written the proofs do not support the claims, and a referee would need substantial new arguments for at least two of the main results. A serious referee could still find value in the upper bounds and the clean parts, but this is not ready for publication. I would reject in current form or require major revision.

Referee Report

6 major / 4 minor

Summary. The manuscript studies the double Roman domination number γ_dR(G) under graph operations. It presents a lower bound for Cartesian products (Theorem 2.2), an upper bound (Theorem 2.4), an exact formula for the 2×n grid (Theorem 2.5), exact values and realizability results for corona products G⊙H (Section 3), bounds and exact values for adding true/false twins (Section 4), and a realizability result for pairs (γ_R, γ_dR) on connected bipartite graphs (Section 5). The main claimed advances are the grid formula and the corona values, which would extend the known theory of double Roman domination to new graph families.

Significance. If the results were correctly proved, they would give the first exact double Roman domination numbers for 2×n grids and several corona families, and would complement known bounds for Roman domination. The paper contains explicit and easily checked upper-bound constructions, and the general upper bound in Theorem 2.4 is a useful observation. However, the lower-bound proofs for the main exact results are not valid as written: several rest on false or unjustified assertions, including the closed-neighborhood partition in Theorem 2.5, the lower-bound claim in Proposition 3.1, and the construction in Proposition 3.3. Since these arguments are load-bearing for the central claims, the current manuscript does not establish its results.

major comments (6)

[§2, Theorem 2.5] The lower-bound proof for odd n asserts that for any dominating set {x_1,...,x_γ} of G_{2,n}, the closed neighborhoods N[x_i] form a partition of the vertex set. This is false: for n=3, the minimum dominating set {(u1,v2),(u2,v2)} has N[(u1,v2)] = {(u1,v1),(u1,v2),(u1,v3),(u2,v2)} and N[(u2,v2)] = {(u2,v1),(u2,v2),(u2,v3),(u1,v2)}, which overlap at two vertices. The claimed lower bound γ_dR(G_{2,n}) ≥ 3(n+1)/2 depends on this partition assertion, so the inequality is not established.
[§2, Theorem 2.2] The proof asserts without justification that the set S_v = (S - {u_i : Z_v^i=1}) ∪ X_v is a dominating set for G. This is false for arbitrary dominating sets: for G=P4 with vertices 1-2-3-4 and S={2,3}, if one removes 2 and X_v={3}, then S_v={3} does not dominate vertex 1. No property of the specific f is supplied that rules out such a configuration. In addition, the chain deriving a strict inequality uses '>' at a point where the preceding display only supports '≥'; hence the strict form of Theorem 2.2 is not proved.
[§3, Proposition 3.1] The lower-bound argument states that 'there are n mutually exclusive copies of H each of which requires at least weight 3 in a DRDF'. This is not true in the form stated: if the attachment vertex u_i in G has value 3, all vertices of the copy H_i may receive value 0, so that copy contributes no positive weight. The total lower bound 3n may still be true, but the argument given does not prove it.
[§3, Proposition 3.3] The constructed function f is not a DRDF. For i=2,...,m+1, the leaf vertex u'_i is assigned 0 while its only neighbor u_i is assigned 2. A vertex with value 0 requires either two neighbors in V2 or one neighbor in V3, so u'_i is not double Roman dominated. Thus the claimed realization of weight 3n-m is invalid, and the statement that every value between 2n+1 and 3n is realizable is not demonstrated.
[§3, Propositions 3.4 and 3.5] The proofs of these exact values are incomplete. Proposition 3.4 asserts the existence of a γ_dR-function of P_n with V2=∅ for n=3k or 3k+2 without construction or proof, and the transformation g is not shown to be a minimum DRDF. Proposition 3.5 says only that the proof is 'similar to that of P_n' and supplies no details. Since these are claimed exact values, the lower bounds are missing.
[§3, Proposition 3.7] The reverse-inequality case analysis contains an error. For k=p+q-1, the displayed inequality g(V)=2(p+q)+1 > 2k+3(p+q-k) is actually an equality, not a strict inequality, so the contradiction does not follow. Consequently the lower bound γ_dR(K_{p,q}⊙K1) ≥ 2(p+q+1) for p,q≥2 is not proved. Also, the case split says 'p,q>2' where the statement covers p,q≥2.

minor comments (4)

[§2, Theorem 2.5] The explicit DRDF formula is not correctly specified: with the printed condition 'k>0' for the i=2 row, the vertex (u1,v1) has no positive neighbor for n=3 and n=5, so the stated f is not a DRDF. If the intended condition is k≥0, the formula and its verification should be corrected.
[§1, Introduction] There are typos: 'vetrtex' should be 'vertex', and '1−1 correspondence' should be 'one-to-one correspondence'.
[§4, Theorem 4.1] The assertion that the case f(u)=2 and f(u')=3 in a γ_dR-function 'won't arise' needs justification; if it can arise, a swap of the values of u and u' would handle it, but this should be stated.
[Figure 1] Figure 1 is referenced in Theorem 2.5 but is not displayed in the manuscript text.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reasoning found; the Theorem 2.5 lower-bound gap is a correctness flaw, not a circularity.

full rationale

The paper's derivation chain is self-contained relative to standard external results. The propositions imported from the literature (1.1–1.4) are not equivalent to the paper's target formulas, and no parameter is fitted to a data subset and then renamed as a prediction. The only author self-citation, in Section 5 for the realizability of (a, a+ceil(a/2)) on paths, is accompanied by independent citations [5] and [10] and is not load-bearing for the new construction in Theorem 5.2. The serious flaw in the lower-bound proof of Theorem 2.5 — the assertion that closed neighborhoods of an arbitrary dominating set of G_{2,n} form a partition — is a false premise that leaves a mathematical gap, but it is not a circular reduction: the claimed value is not defined in terms of itself, nor does the proof assume the conclusion. Similarly, statements such as 'It is easy to verify that these functions are in fact minimum' in Section 5 are omitted justifications, not circular imports. No step in the paper reduces by construction to its own inputs, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rely on several external lemmas from the cited literature (Beeler-Haynes-Hedetniemi, Ahangar et al.) and on unproved structural assertions, most importantly the closed-neighborhood partition assumption in Theorem 2.5 and the per-copy weight lower bound in Proposition 3.1.

assumptions (6)

domain assumption In a minimum-weight DRDF, no vertex needs to be assigned value 1 (Proposition 1.1, from [5]).
This lemma from the prior literature restricts the search space to values {0,2,3} and is used throughout the paper.
domain assumption For any graph G, 2 gamma(G) <= gamma_dR(G) <= 3 gamma(G) (Proposition 1.2, from [5]).
This known bound is used in the proof of Proposition 2.1 and Corollary 2.3.
domain assumption For any non-trivial connected graph, gamma_R(G) < gamma_dR(G) < 2 gamma_R(G) (Proposition 1.4, from [5]).
This known inequality frames the realizability results in Section 5.
ad hoc to paper The closed neighborhoods of any dominating set of the 2 x n grid form a vertex partition (Theorem 2.5 lower-bound proof).
This unproved structural assertion is false: in the 2 x 3 grid, the dominating set {a2, b2} has overlapping closed neighborhoods. The lower-bound proof depends on it.
ad hoc to paper Each copy of H in the corona G circle H requires weight at least 3 in any DRDF (Proposition 3.1).
The paper does not prove this, and support vertices in G may contribute to dominating H-copy vertices, so the per-copy lower bound is not immediate.
ad hoc to paper The constructed functions in Section 3 realize the claimed values and are minimum (Propositions 3.3, 3.4, 3.5).
Several constructions are asserted to be gamma_dR-functions without a full minimality proof, and at least one construction in Proposition 3.3 fails the definition of a DRDF.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Impact of Some Graph Operations on Double Roman Domination Number." pith.science (2026). https://pith.science/paper/YPBT2POQ

@misc{pith2026190806859,
  author       = {Pith},
  title        = {Pith review of: Impact of Some Graph Operations on Double Roman Domination Number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YPBT2POQ}},
  note         = {Machine review of arXiv:1908.06859}
}

abstract

Given a graph $G=(V,E)$, a function $f:V\rightarrow \{0,1,2,3\}$ having the property that if $f(v)=0$, then there exist $ v_{1},v_{2}\in N(v)$ such that $f(v_{1})=f(v_{2})=2$ or there exists $ w \in N(v)$ such that $f(w)=3$, and if $f(v)=1$, then there exists $ w \in N(v)$ such that $f(w)\geq 2$ is called a double Roman dominating function (DRDF). The weight of a DRDF $f$ is the sum $f(V)=\sum_{v\in V}f(v)$. The double Roman domination number, $\gamma_{dR}(G)$, is the minimum among the weights of DRDFs on $G$. In this paper, we study the impact of some graph operations, such as cartesian product, addition of twins and corona with a graph, on double Roman domination number.

Figures

Figures reproduced from arXiv: 1908.06859 by the authors.

**Figure 1.** DRDF f for G2,n, n = 1, 3, 4, 5. Black circles denote vertices in V3, grey circle denote vertex in V2 and empty circles denote vertices in V0. For the reverse inequality, let {x1, x2, . . . , xγ} be any dominating set for G2,n. If n is odd, {N[x1], N[x2], . . . , N[xγ]} is a partition of vertex set of G2,n and |N[xi ]| > 3, for i = 1, 2, . . . , γ. So we have to give 3 to each xi , i = 1, 2, . . . , γ, 7 [PITH_FULL… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

[1]

H. A. Ahangar, M. A. Henning, V. Samodivkin, I. G. Yero, Total Roman Domination in Graphs , Appl. Anal. Discrete Math., 10 (2016), 501-517

work page 2016
[2]

Amjadi, S

J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami, L. Volkmann, An Upper Bound on the Double Roman Domination Number , J. Comb. Optim., https://doi.org/10.1007/s 10878-018-0286-6

doi:10.1007/s
[3]

Math., 244 (2018), 198-204

Anu V., Aparna Lakshmanan S., Double Roman Domination Number , Dis- crete Appl. Math., 244 (2018), 198-204

work page 2018
[4]

Balakrishnan, K

R. Balakrishnan, K. Ranganathan, A Text Book of Graph Theory , Springer, (2000)

work page 2000
[5]

R. A. Beeler, T. W. Haynes, S. T. Hedetniemi, Double Roman Domination , Discrete Appl. Math., 211(1) (2016), 23-29

work page 2016
[6]

E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi, S. T. Hedetniemi, Roman Domination in Graphs , Discrete Math., 278 (2004), 11-12

work page 2004
[7]

C. D. Godsil, B. D. McKay, A New Graph Product and its Spectrum , Bull. Aust. Math. Soc., 18 (1978), 21-28

work page 1978
[8]

G. Hao, X. Chen, L. Volkmann, Double Roman Domination in Digraphs , Bull. Malays. Math. Sci. Soc., http://doi.org/10.1007/s40840-017-0582-9

work page doi:10.1007/s40840-017-0582-9

Show all 12 references

[9]

Volkmann, Double Roman Domination and Domatic Numbers of Graphs , Commun

L. Volkmann, Double Roman Domination and Domatic Numbers of Graphs , Commun. Comb. Optim., 3(1) (2018), 71-77. 14

2018
[10]

Xu, Roman Domination , http://www.math.uchicago

L. Xu, Roman Domination , http://www.math.uchicago. edu/ may/REUPapers/Xu, Linfeng.pdf (manuscript)
[11]

Wu, An Improvement on Vizing’s Conjecture , Inform

Y. Wu, An Improvement on Vizing’s Conjecture , Inform. Process. Lett., 113(3) (2013), 87-88

2013
[12]

I. G. Yero, J. A. Rodr´ ıguez-Vel´ azquez, Roman Domination in Cartesian Product Graphs and Strong Product Graphs , Appl. Anal. Discrete Math., 7(2) (2013), 262-274. 15

2013

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

H. A. Ahangar, M. A. Henning, V. Samodivkin, I. G. Yero, Total Roman Domination in Graphs , Appl. Anal. Discrete Math., 10 (2016), 501-517

work page 2016

[2] [2]

Amjadi, S

J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami, L. Volkmann, An Upper Bound on the Double Roman Domination Number , J. Comb. Optim., https://doi.org/10.1007/s 10878-018-0286-6

doi:10.1007/s

[3] [3]

Math., 244 (2018), 198-204

Anu V., Aparna Lakshmanan S., Double Roman Domination Number , Dis- crete Appl. Math., 244 (2018), 198-204

work page 2018

[4] [4]

Balakrishnan, K

R. Balakrishnan, K. Ranganathan, A Text Book of Graph Theory , Springer, (2000)

work page 2000

[5] [5]

R. A. Beeler, T. W. Haynes, S. T. Hedetniemi, Double Roman Domination , Discrete Appl. Math., 211(1) (2016), 23-29

work page 2016

[6] [6]

E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi, S. T. Hedetniemi, Roman Domination in Graphs , Discrete Math., 278 (2004), 11-12

work page 2004

[7] [7]

C. D. Godsil, B. D. McKay, A New Graph Product and its Spectrum , Bull. Aust. Math. Soc., 18 (1978), 21-28

work page 1978

[8] [8]

G. Hao, X. Chen, L. Volkmann, Double Roman Domination in Digraphs , Bull. Malays. Math. Sci. Soc., http://doi.org/10.1007/s40840-017-0582-9

work page doi:10.1007/s40840-017-0582-9