Outer independent double Roman domination number of graphs

Babak Samadi; Doost Ali Mojdeh; Ismael G. Yero; Zehui Shao

REVIEW 4 major objections 4 minor 12 references

Outer independent double Roman domination number of graphs

T0 review · 4 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 This paper proves the outer independent double Roman domination decision problem is NP-complete even for planar graphs of maximum degree at most four, and gives structural formulas for small and tree cases.

desk verdict Solid new results on a niche parameter, but with a false equality claim in Theorem 6 and an invalid sharpness example in Theorem 10; the corona formula proof is actually sound. read the letter →

arxiv 1909.01775 v1 pith:7462XPVI submitted 2019-08-20 math.GM

Doost Ali Mojdeh , Babak Samadi , Zehui Shao , Ismael G. Yero This is my paper · ORCID

classification math.GM MSC 05C69

keywords outerindependentdoubleRomandominationNP-completeplanargraphsvertexcovernumberindependencecorona

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

An outer independent double Roman dominating function is a labeling $f:V(G)\to\{0,1,2,3\}$ in which every vertex labeled $0$ has either one neighbor labeled $3$ or two neighbors labeled $2$, every vertex labeled $1$ has a neighbor labeled at least $2$, and the set of vertices labeled $0$ is independent; its weight is $\sum_v f(v)$, and $\gamma_{oidR}(G)$ is the minimum possible weight. The paper proves that deciding whether $\gamma_{oidR}(G)\le k$ is NP-complete even for planar graphs with maximum degree at most four, by a reduction from the independence number problem on planar graphs with maximum degree at most three. It also characterizes all connected graphs with $\gamma_{oidR}(G)\in\{3,4,5\}$, proves tight bounds relating $\gamma_{oidR}(G)$ to the domination, independence, and vertex-cover numbers, establishes $\gamma_{oidR}(T)\ge 2\beta(T)+1$ for every tree, and gives an exact corona-product formula. A sympathetic reader would care because this pins a recently introduced labeling parameter into the classical framework of Roman-type domination and shows that its computation remains hard under strong planarity and degree restrictions, while also giving structural descriptions of the graphs where the parameter is small.

What carries the argument

The central object is the OIDRD function itself, viewed as a partition $(V_0,V_1,V_2,V_3)$ of the vertex set with $V_0$ independent; the constraints are that every vertex in $V_0$ has a neighbor in $V_3$ or two neighbors in $V_2$, and every vertex in $V_1$ has a neighbor in $V_2\cup V_3$. The reduction gadget carries the NP-completeness proof: from a planar degree-$3$ graph $G$, attach to each $v_i$ a private central vertex $u_i$ with two leaves and the edge $v_iu_i$, producing a planar degree-$4$ graph $G'$; optimality forces $f(u_i)=3$ and $0$ on its two leaves, so the identity $\gamma_{oidR}(G')=4n-\alpha(G)$ reduces the decision problem to independence number. The structural results for small parameters and the tree bounds are driven by the same partition, together with local weight-preserving reassignments of labels along paths.

What would settle it

Exhaustively compute $\gamma_{oidR}(T)$ for all trees with, say, at most 15 vertices and compare each with $2\beta(T)+1$; even one tree with $\gamma_{oidR}(T)<2\beta(T)+1$ would refute Theorem 11. If none appears, inspect the normalization step in Subcase 2.2 of the tree proof: find a tree in which every optimal function on a longest path assigns 0 to the parent but no weight-preserving rearrangement puts 3 on the support vertex and 0 on the leaf, which would pinpoint where the proof's 'we can assume' fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that the outer independent double Roman domination number has a precise structural and computational profile. For any connected graph $G$ of order $n\ge 2$ and maximum degree $\Delta$, the parameter satisfies $\max\{\gamma(G), \frac{2}{\Delta}\alpha(G)\}+\beta(G)\le \gamma_{oidR}(G)\le 3\beta(G)$, and the bounds are sharp; moreover $\gamma_{oiR}(G)<\gamma_{oidR}(G)<2\gamma_{oiR}(G)$. For the decision problem, the paper constructs, from a planar graph $G$ of maximum degree at most $3$, a planar graph $G'$ of maximum degree at most $4$ by giving each vertex $v_i$ a private central vertex $u_i$ with two leaves and the edge $v_iu_i$. It then shows any optimal OIDRD function must assign $3$ to every $u_i$ and $0$ to its two leaves, so the only freedom lies in labeling $V(G)$; the resulting identity $\gamma_{oidR}(G')=4n-\alpha(G)$ transfers NP-completeness from the independence number problem. For trees the paper proves $\gamma_{oidR}(T)\ge 2\beta(T)+1$ by induction, with equality on even-order paths, and for corona products $G\odot H$ with $\Delta(H)\le |V(H)|-2$ it gives an exact formula obtained by minimizing a four-term expression over labelings of $V(G)$ whose zero set is independent. The characterizations of connected graphs with parameter $3$, $4$, or $5$ come from a case analysis on the partition $(V_0,V_1,V_2,V_3)$ forced by an optimal function.

Load-bearing premise

The tree lower bound depends on a local normalization: in an optimal labeling along a longest leaf-to-leaf path, after assuming a parent vertex is labeled 0, the proof asserts 'we can assume' the next support vertex is labeled 3 and the leaf 0; if this rearrangement is not always possible without increasing weight or disturbing the constraints elsewhere, the induction proving $\gamma_{oidR}(T)\ge 2\beta(T)+1$ collapses.

Editorial extensions

If this is right

For planar graphs with maximum degree at most four, no polynomial-time algorithm computes $\gamma_{oidR}$ unless P=NP, and the hardness extends automatically to every graph class containing these planar graphs.
In every nontrivial connected graph the parameter is strictly squeezed between $\gamma_{oiR}(G)$ and $2\gamma_{oiR}(G)$, so any algorithm or bound for outer independent Roman domination transfers to OIDRD up to a factor of two.
The tree inequality $\gamma_{oidR}(T)\ge 2\beta(T)+1$, tight on even paths, makes the vertex cover number a directly usable lower bound when designing trees with prescribed OIDRD weight.
For corona products $G\odot H$ with $\Delta(H)\le |V(H)|-2$, the exact formula reduces evaluation of the parameter to four simpler invariants of $H$ and a minimization over independent-labelings of $G$.
The full descriptions of connected graphs with $\gamma_{oidR}\in\{3,4,5\}$ provide a finite recognition procedure for small parameter values.

Reading between the lines

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

Because the reduction gives the exact identity $\gamma_{oidR}(G')=4n-\alpha(G)$, the OIDRD number encodes the independence number on the constructed graphs; approximation hardness and parameterized complexity results for independent set are therefore likely to transfer to OIDRD, a consequence the paper leaves implicit.
The tree proof's local reassignments suggest a natural next question: characterize all trees attaining $\gamma_{oidR}(T)=2\beta(T)+1$, not only even paths; the induction machinery appears designed for such a classification.
The NP-completeness proof stops at maximum degree four, leaving open whether the problem remains hard for planar graphs of maximum degree three; the gadget itself changes degree of each original vertex from $d$ to $d+1$, so this is a separate question.
The corona formula implies that for graphs built by wide corona products, $\gamma_{oidR}$ can be computed by a small dynamic program over the base graph using the four invariants of $H$; this algorithmic use is not stated in the paper.

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

The paper has a real core. The planar NP-completeness result (Theorem 5) is a clean reduction from independent set on planar max-degree-3 graphs, and the bound is exactly right. The tree lower bound 2β(T)+1 (Theorem 11) is plausible and, after a bit of work, the WLOG step in Subcase 2.2 can be justified by a local swap (when x=0, v=1, w=2, switch to w=3, v=0 without changing weight). The corona formula (Theorem 12) is also correct; a stress-test worry to the contrary does not hold up. The alleged counterexample (0,2,0,1) on P4 is in fact a valid OIRD function—label 1 has no condition in Roman domination—and the restriction to an H-copy is OIRD because each 0-vertex has vi as one 2-neighbor and therefore must have another 2-neighbor inside H. So that proof is fine.

The soft spots are real but circumscribed. Theorem 6 claims γ_oidR(G) = 2γ_oiR(G) iff G = K_n. That is false twice over: for K_n, γ_oidR = n+1 and γ_oiR = n, so equality never holds, and the proof actually shows G must be edgeless before incorrectly concluding it is complete. This also contradicts the paper's own Corollary 9. Theorem 10's upper-bound sharpness example uses G′ ⊙ K_r with all vertices of each K_r copy labeled 0, but those vertices are adjacent, so V0 is not independent—the example is invalid. The upper bound itself is sharp (stars work), so the claim survives, but the supporting example needs replacement.

The characterizations in Proposition 3 are intricate and the case analysis looks defensible, though I did not verify every subcase. The paper cites prior work properly, including the paper that introduced the parameter, and the self-citations are not problematic.

Who is this for? Researchers in domination theory who want the planar NP-completeness and the exact corona formula. The errors are not load-bearing for the main advertised results, but they are real and need correction. I would send this to a serious referee, expecting a revision that fixes Theorem 6, replaces the upper-bound example, and tightens the tree proof's normalization argument.

Referee Report

4 major / 4 minor

Summary. The paper defines outer independent double Roman domination (OIDRD) and studies it systematically. It characterizes all connected graphs with OIDRD number 3, 4, or 5; proves that the OIDRD decision problem is NP-complete for planar graphs of maximum degree at most four; derives upper and lower bounds relating the parameter to the domination number, independence number, vertex cover number, and outer independent Roman domination number; proves the lower bound gamma_oidR(T) >= 2 beta(T) + 1 for trees; and gives an exact formula for gamma_oidR(G ⊙ H) under a maximum-degree condition on H. The principal advertised results are Theorem 5 (NP-completeness), Theorem 10 (bounds), Theorem 11 (tree bound), and Theorem 12 (corona formula).

Significance. The NP-completeness reduction in Section 3 is the strongest part of the paper: the reduction from planar IN to OIDRD is clean, and the lower and upper bounds in the reduction are essentially correct. If the corona formula in Theorem 12 can be proved with a corrected Case 3 argument, it would be a useful exact result for a natural graph operation. The tree lower bound is also of interest. However, the manuscript currently contains a false equality characterization in Theorem 6, an invalid sharpness example in Theorem 10, an under-justified normalization step in the proof of Theorem 11, and a false assertion in the lower-bound proof of Theorem 12. These issues affect advertised claims and must be repaired before the paper is publishable.

major comments (4)

[Section 3 (Theorem 6)] The equality characterization in Theorem 6 is false as stated. The proof asserts 'Clearly, gamma_oidR(K_n) = 2 gamma_oiR(K_n) = 2n', which contradicts Observation 1(iii), where gamma_oidR(K_n) = n+1, and also contradicts Corollary 9, which states that gamma_oiR(G) < gamma_oidR(G) < 2 gamma_oiR(G) for every nontrivial connected graph. In fact, the argument given shows that equality in gamma_oidR(G) <= 2 gamma_oiR(G) forces G to have no edges, so the equality case is the edgeless graph, not the complete graph. The statement and proof need to be corrected.
[Section 3 (Theorem 10)] The sharpness example for the upper bound gamma_oidR(G) <= 3 beta(G) is invalid. In the proposed example G' ⊙ K_r with r >= 2, assigning f(v') = 3 to every v' in V(G') and f(v) = 0 to every vertex v of each K_r copy makes V_0 contain a clique of size r, so V_0 is not independent and f is not an OIDRD function. This invalidates the claimed tightness construction as written. The bound itself remains true and is sharp for stars, so the example should be replaced.
[Section 4 (Theorem 11)] The proof of the tree lower bound contains an unjustified 'without loss of generality' step. In Subcase 2.2, after assuming f(x) = 0, the proof states 'we can assume that f(w) = 3 and f(v) = 0' without showing that every gamma_oidR(T)-function can be locally transformed into this form. A minimum function could, for instance, satisfy f(w) = 2 and f(v) = 1, and the subsequent case analysis in Subsubcases 2.2.1 through 2.2.4 depends on the chosen normalization. The same issue appears in the f(x) = 0 and f(x) = 1 parts of Subcase 2.1. A weight-preserving transformation argument is needed.
[Section 5 (Theorem 12)] Case 3 of the lower-bound proof is false. The claim that the restriction of g to H_i 'must be an OIRD function of H_i' fails because a vertex of H_i labeled 0 may use g(v_i) = 2 as one of its two required neighbors in V_2, and a vertex labeled 1 may use v_i to satisfy its requirement. For example, take G = K_1 and H = P_4, which satisfies Delta(P_4) = 2 <= 4 - 2. Let v be the G-vertex and label the P_4 copy (x1, x2, x3, x4) as (0, 2, 0, 1), with f(v) = 2. This is an OIDRD function of K_1 ⊙ P_4 of weight 5, and a short check shows gamma_oidR(K_1 ⊙ P_4) = 5. The restriction to the P_4 copy is (0, 2, 0, 1), which is not an OIRD function of P_4 because x4 has label 1 and its only P_4 neighbor x3 has label 0. The per-copy bound gamma_oiR(H) + 2 = 6 is therefore violated. The lower-bound half of Theorem 12 is not proved as written; a corrected Case 3 argument is required.

minor comments (4)

[Section 3 (Theorem 5)] The last sentence of the proof says 'we deduce that the OITRD problem is NP-complete'; this should read 'OIDRD problem'.
[Introduction] The sentence defining the parameter is garbled: 'The (outer independent) double Roman domination number (gamma_oidR(G)) gamma_dR(G) equals the minimum weight of (an) a (OIDRD function) DRD function of G.' This should be rewritten for clarity.
[Section 3 (Theorem 10)] In the second part of the lower-bound proof, the text says 'every vertex in S' has at least two neighbors in V_0'; from the surrounding inequality, this should be 'at least two neighbors in V_2'.
[Section 3 (Theorem 10)] The sharpness construction for the lower bound (2) says 'form a cycle on the set of vertices {z1, ..., z_t}'; this requires t >= 3 to define a simple cycle, and that condition should be stated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain is self-contained and the central results are proved by direct construction, induction, and external NP-completeness reductions.

full rationale

The paper's central claims are not derived from themselves. Theorem 5 reduces the OIDRD problem to the IN dependence number problem on planar graphs of maximum degree at most three, citing Garey and Johnson, and establishes the explicit equality gamma_oidR(G') = 4n - alpha(G) via a direct construction and lower-bound argument; this is an external reduction, not a self-referential one. Proposition 3 and Theorem 11 are proved by explicit case analysis and induction, using only standard parameter definitions and, in the tree proof, the externally cited path values from [2]. The bounds in Theorems 6 and 10 are derived from elementary inequalities and well-known facts such as Gallai's theorem. The corona formula in Theorem 12 is argued by giving an explicit upper-bound construction and a lower-bound case analysis over the restriction of an optimal function; while the proof may contain a correctness gap in Case 3, that gap is not circularity, because the argument does not assume the formula being proved. The self-citations [5] and [12] appear only in introductory or contextual remarks and are not load-bearing for any main theorem. Accordingly, the paper exhibits no circular step that reduces a prediction or theorem to its own input.

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

The paper has no fitted parameters and introduces no new entities. It rests on standard graph theory results: Gallai's identity relating independence and vertex cover numbers, and the NP-completeness of the independence number problem on planar graphs of maximum degree three. It also relies on the prior introduction and basic values of the OIDRD parameter from Ahangar et al. [2].

assumptions (3)

standard math Gallai's theorem: alpha(G)+beta(G)=n for every graph G.
Invoked in Theorem 10 to convert n-alpha to beta, and in Theorem 12 in the corona formula derivation.
standard math The independence number decision problem is NP-complete for planar graphs with maximum degree at most three (Garey and Johnson [8]).
Used as the source problem in the NP-completeness reduction in Theorem 5.
domain assumption Basic properties of OIDRD functions as established in [2], including the values of gamma_oidR on paths, cycles, and complete graphs (Observation 1(i)-(iii)).
Observation 1(i)-(iii) are quoted from [2] and used in the bounds and examples throughout the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Outer independent double Roman domination number of graphs." pith.science (2026). https://pith.science/paper/7462XPVI

@misc{pith2026190901775,
  author       = {Pith},
  title        = {Pith review of: Outer independent double Roman domination number of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7462XPVI}},
  note         = {Machine review of arXiv:1909.01775}
}

abstract

A double Roman dominating function of a graph $G$ is a function $f:V(G)\rightarrow \{0,1,2,3\}$ having the property that for each vertex $v$ with $f(v)=0$, there exists $u\in N(v)$ with $f(u)=3$, or there are $u,w\in N(v)$ with $f(u)=f(w)=2$, and if $f(v)=1$, then $v$ is adjacent to a vertex assigned at least $2$ under $f$. The double Roman domination number $\gamma_{dR}(G)$ is the minimum weight $f(V(G))=\sum_{v\in V(G)}f(v)$ among all double Roman dominating functions of $G$. An outer independent double Roman dominating function is a double Roman dominating function $f$ for which the set of vertices assigned $0$ under $f$ is independent. The outer independent double Roman domination number $\gamma_{oidR}(G)$ is the minimum weight taken over all outer independent double Roman dominating functions of $G$. In this work, we present some contributions to the study of outer independent double Roman domination in graphs. Characterizations of the families of all connected graphs with small outer independent double Roman domination numbers, and tight lower and upper bounds on this parameter are given. We moreover bound this parameter for a tree $T$ from below by two times the vertex cover number of $T$ plus one. We also prove that the decision problem associated with $\gamma_{oidR}(G)$ is NP-complete even when restricted to planar graphs with maximum degree at most four. Finally, we give an exact formula for this parameter concerning the corona graphs.

Figures

Figures reproduced from arXiv: 1909.01775 by the authors.

**Figure 1.** The graphs G1, G2 and G3. 2 Connected graphs with small OIDRD numbers In this section, we characterize the family of all connected graphs G for which γoidR(G) ∈ {3, 4, 5}. To this end, let G be the family of all graphs of the form G1, G2 and G3 depicted in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 2.** The family of graphs G ′ . Corollary 7. If G is a connected graph and f = (V0, V1, V2) is a γoiR(G)-function, then γoidR(G) ≤ 2γoiR(G) − |V2|. For the equality in the upper bound given in Corollary 7, consider the family of stars, bistars and the family of graphs G ′ depicted in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Ahangar, M

H.A. Ahangar, M. Chellali and V. Samodivkin, Outer independent Roman dominating func- tions in graphs , Int. J. Comput. Math. 94 (2017), 2547–2557

work page 2017
[2]

Ahangar, M

H.A. Ahangar, M. Chellali and S.M. Sheikholeslami, Outer independent double Roman dom- ination, Appl. Math. Comput., doi: 10.1016/j.amc.2019.124617

work page arXiv 2019
[3]

Anu and A

V. Anu and A. Lakshmanan, Double Roman domination number , Discrete Appl. Math. 244 (2018), 198–204

work page 2018
[4]

Beeler, T.W

R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination , Discrete Appl. Math. 211 (2016), 23–29

work page 2016
[5]

Cabrera Mart ´ ınez, D

A. Cabrera Mart ´ ınez, D. Kuziak and I.G. Yero, Outer-independent total Roman domination in graphs, Discrete Appl. Math., doi: 10.1016/j.dam.2018.12.018

work page doi:10.1016/j.dam.2018.12.018 2018
[6]

Cockayne, P.A

E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hed etniemi, Roman domination in graphs, Discrete Math. 278 (2004), 11–22

work page 2004
[7]

Gallai, ¨Uber extreme Punkt-und Kantenmengen , Ann

T. Gallai, ¨Uber extreme Punkt-und Kantenmengen , Ann. Univ. Sci. Budapest E¨ otv¨ os Sect. Math. 2 (1959), 133–138

work page 1959
[8]

Garey and D.S

M.R. Garey and D.S. Johnson, Computers and intractabili ty: A guide to the theory of NP-completeness, W.H. Freeman & Co., New York, USA, 1979

work page 1979

Show all 12 references

[9]

Jafari Rad and H

N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs , Discuss. Math. Graph Theory, 39 (2018), 41–53

2018
[10]

Stewart, Defend the Roman Empire! , Sci

I. Stewart, Defend the Roman Empire! , Sci. Amer. 281 (1999), 136–139

1999
[11]

West, Introduction to graph theory, 2nd ed., Prent ice Hall, USA, 2001

D.B. West, Introduction to graph theory, 2nd ed., Prent ice Hall, USA, 2001

2001
[12]

Zhang, Z

X. Zhang, Z. Li, H. Jiang and Z. Shao, Double Roman domination in trees , Inf. Process. Lett. 134 (2018), 31–34. 14

2018

Pith tools

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

[1] [1]

Ahangar, M

H.A. Ahangar, M. Chellali and V. Samodivkin, Outer independent Roman dominating func- tions in graphs , Int. J. Comput. Math. 94 (2017), 2547–2557

work page 2017

[2] [2]

Ahangar, M

H.A. Ahangar, M. Chellali and S.M. Sheikholeslami, Outer independent double Roman dom- ination, Appl. Math. Comput., doi: 10.1016/j.amc.2019.124617

work page arXiv 2019

[3] [3]

Anu and A

V. Anu and A. Lakshmanan, Double Roman domination number , Discrete Appl. Math. 244 (2018), 198–204

work page 2018

[4] [4]

Beeler, T.W

R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination , Discrete Appl. Math. 211 (2016), 23–29

work page 2016

[5] [5]

Cabrera Mart ´ ınez, D

A. Cabrera Mart ´ ınez, D. Kuziak and I.G. Yero, Outer-independent total Roman domination in graphs, Discrete Appl. Math., doi: 10.1016/j.dam.2018.12.018

work page doi:10.1016/j.dam.2018.12.018 2018

[6] [6]

Cockayne, P.A

E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hed etniemi, Roman domination in graphs, Discrete Math. 278 (2004), 11–22

work page 2004

[7] [7]

Gallai, ¨Uber extreme Punkt-und Kantenmengen , Ann

T. Gallai, ¨Uber extreme Punkt-und Kantenmengen , Ann. Univ. Sci. Budapest E¨ otv¨ os Sect. Math. 2 (1959), 133–138

work page 1959

[8] [8]

Garey and D.S

M.R. Garey and D.S. Johnson, Computers and intractabili ty: A guide to the theory of NP-completeness, W.H. Freeman & Co., New York, USA, 1979

work page 1979