{"id":"8bfbb58d-3862-4c45-bd6b-f61359dad52e","arxiv_id":"1909.01775","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The outer independent double Roman domination number is characterized for small values, proven NP-complete on planar graphs of maximum degree four, and computed exactly for corona graphs.","lead":"This paper studies a variant of double Roman domination on graphs, where vertices with zero legions cannot be adjacent to each other. It characterizes small values, proves a planar NP-completeness result, bounds trees, and gives an exact formula for corona graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 12's lower-bound proof is invalid: in Case 3, the restriction of a minimum OIDRD function to an H-copy need not be an OIRD function, so the corona formula is not established by the argument given.","rationale":"The NP-completeness reduction in Theorem 5 appears sound: the gadget bound of 3 per ui-triple and the independent-zero restriction on the original vertices correctly give γ_oidR(G′)=4n−α(G). The reader's identified weakest assumption, the WLOG normalization in the tree proof, is a genuine gap but seems repairable: when f(w)+f(v)=3 and f(x)≤1, the local swap to (f(w),f(v))=(3,0) preserves weight and validity. The more serious defect is in Theorem 12, where the proof's Case 3 assertion is not merely unjustified but false, as the K1⊙P4 example shows. This is an internal inconsistency in the proof of a central advertised result, not a disagreement with external consensus. The reader's other noted errors (Theorem 6 equality case, Theorem 10 sharpness example) are real but secondary. Because the corona formula may still be true and the main structural results are plausible, the appropriate verdict remains conditional pending a corrected proof of Theorem 12.","tokens_in":14199,"tokens_out":29614,"duration_ms":323705,"concrete_test":"Re-derive the lower-bound half of Theorem 12 without the Case-3 restriction claim, and verify the formula by exhaustive computation for all G with at most 4 vertices and all H with Δ(H) ≤ |V(H)|−2 and |V(H)| ≤ 7. The instance G=K1, H=P4 already refutes the proof's per-copy inequality, so the decisive question is whether a corrected lower bound can recover the stated minimum on all small instances; if the formula fails on any exhaustive instance, Theorem 12 should be weakened or corrected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The corona formula is a central advertised result, and its proof contains a concrete false assertion. In Theorem 12, Case 3, the authors claim that if g(vi)=2, then after eliminating labels 3 inside Hi, the restriction of g to Hi 'must be an OIRD function of Hi'. This is false. Take G=K1 and H=P4, which satisfies Δ(P4)=2≤4−2. Let v be the G-vertex and label the P4 copy (x1,x2,x3,x4) as (0,2,0,1), with f(v)=2. This is an OIDRD function of K1⊙P4 of weight 2+3=5, and a short case check shows γ_oidR(K1⊙P4)=5. The restriction to the P4 copy is (0,2,0,1), which is not an OIRD function of P4: the vertex x4 has label 1 and its only P4 neighbor x3 has label 0. Since γ_oiR(P4)=4, the claimed per-copy lower bound g(V(Hi)∪{v}) ≥ γ_oiR(H)+2 = 6 fails; the actual contribution is 5. Thus the lower-bound half of Theorem 12 as written does not follow. The stated formula may still be true (for this instance, the minimum over fG is also 5 via fG(v)=3 and labels (0,1,0,1) on the P4 copy), but the proof needs a corrected Case 3 argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":14417,"tokens_out":22137,"duration_ms":225362,"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":[{"comment":"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":"Section 3 (Theorem 6)"},{"comment":"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":"Section 3 (Theorem 10)"},{"comment":"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":"Section 4 (Theorem 11)"},{"comment":"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.","section":"Section 5 (Theorem 12)"}],"minor_comments":[{"comment":"The last sentence of the proof says 'we deduce that the OITRD problem is NP-complete'; this should read 'OIDRD problem'.","section":"Section 3 (Theorem 5)"},{"comment":"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":"Introduction"},{"comment":"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":"Section 3 (Theorem 10)"},{"comment":"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.","section":"Section 3 (Theorem 10)"}],"recommendation":"major_revision","confidential_remarks":"The NP-completeness reduction and the upper-bound constructions are the strongest parts of the manuscript. The main obstacles are the false equality statement in Theorem 6, the invalid sharpness example in Theorem 10, the unjustified WLOG normalization in Theorem 11, and the false Case 3 assertion in Theorem 12. All of these appear to be fixable in revision, and I do not see grounds for rejection if the authors provide corrected proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":15021,"tokens_out":16313,"would_cite":true,"duration_ms":154580,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["outer independent double Roman domination","double Roman domination","Roman domination","NP-complete","planar graphs","vertex cover number","independence number","corona graphs"],"falsifier":"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.","tokens_in":13944,"feed_emoji":"📐","tokens_out":11855,"duration_ms":105961,"temperature":0.7,"pith_summary":"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.","feed_headline":"Deciding OIDRD is NP-complete even for planar graphs of degree 4","feed_subtitle":"Outer independent double Roman domination asks for the cheapest 0/1/2/3 labeling; the paper ties this hard problem to the independence…","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduces the outer independent double Roman domination parameter and contributes the baseline observations and prior NP-hardness results that this paper extends.","marker":"[2]"},{"why":"supplies the NP-completeness of the independence number problem on planar graphs with maximum degree at most three, the source of the reduction in Theorem 5.","marker":"[8]"},{"why":"defines double Roman domination, the base concept whose outer-independent variant is studied throughout.","marker":"[4]"},{"why":"introduces outer independent Roman domination, the parameter compared with $\\gamma_{oidR}$ in Theorems 6 and 8.","marker":"[1]"},{"why":"defines Roman domination and establishes the general framework that motivates double Roman variants.","marker":"[6]"},{"why":"provides the identity $\\alpha(G)+\\beta(G)=|V(G)|$ used in the bounds of Theorem 10.","marker":"[7]"}],"fun_headline_variants":["OIDRD NP-complete even for planar degree-4 graphs","Tight bounds and characterizations for OIDRD","Tree OIDRD bound: at least 2*vertex cover + 1","Exact OIDRD formula for corona products","Small OIDRD numbers characterize graph families"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["OIDRD NP-complete even for planar degree-4 graphs","Tight bounds and characterizations for OIDRD","Tree OIDRD bound: at least 2*vertex cover + 1","Exact OIDRD formula for corona products","Small OIDRD numbers characterize graph families"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000842,"raw_usage":{"total_tokens":3817,"prompt_tokens":1241,"completion_tokens":2576,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":857,"completion_tokens_details":{"reasoning_tokens":2494}},"tokens_in":857,"tokens_out":2576,"duration_ms":19986,"temperature":1.0,"reasoning_tokens":2494,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:23:12.174029+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Ahangar, M","cited_arxiv_id":null,"evidence_quote":"introduces the outer independent double Roman domination parameter and contributes the baseline observations and prior NP-hardness results that this paper extends."},{"cited_title":"Garey and D.S","cited_arxiv_id":null,"evidence_quote":"supplies the NP-completeness of the independence number problem on planar graphs with maximum degree at most three, the source of the reduction in Theorem 5."},{"cited_title":"Beeler, T.W","cited_arxiv_id":null,"evidence_quote":"defines double Roman domination, the base concept whose outer-independent variant is studied throughout."},{"cited_title":"Ahangar, M","cited_arxiv_id":null,"evidence_quote":"introduces outer independent Roman domination, the parameter compared with $\\gamma_{oidR}$ in Theorems 6 and 8."},{"cited_title":"Cockayne, P.A","cited_arxiv_id":null,"evidence_quote":"defines Roman domination and establishes the general framework that motivates double Roman variants."},{"cited_title":"Gallai, ¨Uber extreme Punkt-und Kantenmengen , Ann","cited_arxiv_id":null,"evidence_quote":"provides the identity $\\alpha(G)+\\beta(G)=|V(G)|$ used in the bounds of Theorem 10."}],"review_version":1}