{"id":"fbfb65b6-6fce-43c2-a624-3780b53a9d6c","arxiv_id":"1908.01432","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every graph G of order n not isomorphic to C5, the 2-rainbow independent domination numbers of G and its complement sum to at most n+2, improving the prior n+3 bound, and the k-rainbow independent domination decision problem is NP-complete for bipartite graphs.","lead":"This paper tightens a bound on the '2-rainbow independent domination' numbers of a graph and its complement, and shows the corresponding decision problem is computationally hard. The results refine a 2018 theorem and add a complexity result for a graph domination variant.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.3's classification proof is incomplete at Observation 3: the step 'By Observation 1, d_G(y3)=1' does not follow from Observation 1, and Theorem 3.5's Case 1 depends on that classification.","rationale":"The reader identified the classification in Theorem 2.4 as the weakest assumption, and my reading converges on the same point. I found a specific place where that classification proof appears to skip a case: Observation 3 asserts d_G(y3)=1 from Observation 1 without treating the possibility that y3 is adjacent to x. Since Observation 2 allows only one 3+-vertex, y3 would then be another 2-vertex in N_G(x), and the local contradiction is not immediate. The proof as printed therefore does not fully justify 'at most two 2-vertices in N_G(x)'. This matters because Theorem 2.3 feeds directly into Theorem 2.4, which is used in Lemma 3.2 and in Case 1 of Theorem 3.5. The improved Nordhaus-Gaddum bound is the paper's central new claim, and no machine-checked verification is supplied, so an unjustified step in the classification is a genuine correctness risk. I am not claiming the theorem is false; the gap may be repairable, and the rest of the proof may be sound. But the current text does not establish the needed classification. For that reason the conditional verdict is appropriate. I also note that the introduction's V0-independence statement is inconsistent with the working definition used later, but that is a textual/definitional defect rather than the main mathematical load-bearing issue. The proposed computational check would settle whether the classification itself is false for small orders; if it passes, the remaining issue is a proof repair rather than a counterexample.","tokens_in":17342,"tokens_out":24369,"duration_ms":267685,"concrete_test":"Exhaustively enumerate all connected graphs on at most 9 vertices and compute gamma_ri2 exactly, either by search over all labelings or by an ILP/SAT model. Check the statement of Theorem 2.3: equality gamma_ri2=|V|-1 should hold exactly for S_{|V|-1}, S^+_{|V|-1}, S(|V|-3,1), and C5. A single graph outside this list with gamma_ri2=|V|-1 would refute the classification and undermine Theorem 3.5's proof. If no counterexample appears, the suspected gap in Observation 3 is likely patchable, but the missing subcase y3 in N_G(x) still needs an explicit proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central upper bound in Theorem 3.5 is proved by contradiction with the known bound n+3. Two of its main ingredients are Lemma 3.2 and Case 1 of Theorem 3.5, both of which invoke Theorem 2.4, the classification of graphs with gamma_ri2=|V|-1. Theorem 2.4 is derived from Theorem 2.3, whose proof is a short structural argument via Observations 1-3. In Observation 3, after assuming that N_G(x) contains three 2-vertices x1,x2,x3, the proof considers x3's second neighbor y3 and asserts 'By Observation 1, d_G(y3)=1'. Observation 1 only says that every 2+-vertex belongs to N_G(x); it does not prohibit y3 from being a neighbor of x. If y3 is adjacent to x, then y3 is another 2-vertex in N_G(x), and the claimed nonedge y1y3 is not justified by the stated observation. The proof then jumps to a local 2RiDF that relies on y1y3 not being an edge. Since the written argument does not treat the case y3 in N_G(x), the classification Theorem 2.3 is not fully established as written. If that classification has an omitted connected graph, then the case analysis for G[V0] in Theorem 3.5, especially in Case 1, would be incomplete and the improved bound could fail. The classification may well be true and repairable, but the gap is load-bearing because the main theorem leans on it directly. No counterexample is claimed here; the concern is that a central proof step is unjustified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the k-rainbow independent domination number γrik(G), introduced by Šumenjak, Rall, and Tepeh. It claims two main results. First, it improves the Nordhaus-Gaddum-type upper bound from n+3 to n+2 for every graph of order n not isomorphic to C5. Second, it proves that the decision problem for k-rainbow independent dominating functions is NP-complete, even for bipartite graphs. The proof of the Nordhaus-Gaddum improvement is carried out only for the case k=2 and relies on a structural classification of graphs with γri2(G)=|V(G)|-1. The NP-completeness proof is a polynomial reduction from the domination problem on bipartite graphs by attaching k-1 leaves to every vertex.","tokens_in":17655,"tokens_out":17472,"duration_ms":178639,"significance":"If the k=2 bound is correct, it is a genuine improvement over the previously known n+3 bound, and the classification of graphs with γri2(G)=|V(G)|-1 is a useful structural contribution. The NP-completeness result extends the algorithmic hardness landscape for rainbow independent domination and is, in outline, a sound reduction. The paper also gives several auxiliary lemmas that are reusable. However, the abstract and conclusion claim the improved bound for all k, while only the k=2 case is proved; this overclaim must be corrected. In addition, the classification proof contains a specific gap that is load-bearing for the main theorem.","major_comments":[{"comment":"The abstract states that the improved bound 5 ≤ γrik(G)+γrik(complement G) ≤ n+2 is shown for graphs not isomorphic to C5, and Section 5 repeats this for the k-rainbow invariant. Section 3, however, proves only the case k=2, namely Theorem 3.5 for γri2. The proof is built on 2-color arguments (for example, Lemma 3.3 and the case analysis in Theorem 3.5) and does not automatically extend to k>2. The manuscript should either prove the general-k statement or explicitly restrict the claimed Nordhaus-Gaddum improvement to k=2.","section":"Abstract and Section 5"},{"comment":"The statement of Theorem 3.5 says that for every graph G of order n≥2 with G not C5, one has 5 ≤ γri2(G)+γri2(complement G) ≤ n+2. This is false for n=2: if G=K2, then γri2(K2)=2 and γri2(2K1)=2, so the sum is 4<5. The proof says the statement holds trivially for n=2, which is incorrect. The theorem should be stated for n≥3, or the lower bound should be adjusted; the error also propagates to the abstract's lower bound.","section":"Theorem 3.5"},{"comment":"In the proof of Observation 3, after defining N_G(x3)={x,y3} and N_G(x1)={x,y1}, the text asserts 'By Observation 1, d_G(y3)=1, i.e., y1y3 is not an edge.' This inference is not justified. Observation 1 only says that every 2+-vertex belongs to N_G(x); it does not imply that y3 has degree 1. If d_G(y3)≥2, then y3 is adjacent to x, so y3 is another 2-vertex in N_G(x), and the required nonedge y1y3 may fail. The displayed function f(x1)=f(x3)=0, f(x)=1, f(y1)=f(y3)=2 then need not be a 2RiDF. This gap is load-bearing: Theorem 2.3 is used in Theorem 2.4, Lemma 3.2, and Case 1 of Theorem 3.5. The classification may be true and repairable, but the written proof is incomplete at this step.","section":"Section 2, Observation 3"}],"minor_comments":[{"comment":"The abstract defines the k-rainbow independent domination number as a set consisting of two vertex-disjoint independent sets V1 and V2. This matches k=2 only; for general k there are k independent sets V1,...,Vk, as correctly stated in Section 1. The definition should be made consistent.","section":"Abstract"},{"comment":"In the converse direction of the reduction, the sentence 'Since f is a kRiDF, it follows that every vertex in V0 is adjacent to at least one vertex in D' is true but needs justification: a vertex in V0 has k-1 leaves, which can cover at most k-1 colors, so at least one color must be supplied by an original neighbor, which lies in D. Please add this argument for readability.","section":"Section 4, Theorem 4.1"},{"comment":"The phrase 'the proof of |V2|≥2 is similar to that of |V2|≥2' should read 'the proof of |V2|≥2 is similar to that of |V1|≥2'.","section":"Lemma 3.3(3)"},{"comment":"The notation 'NG{u,v}=∅' is nonstandard and likely means that u and v have no common neighbor; please clarify the notation, e.g., N_G(u)∩N_G(v)=∅.","section":"Lemma 3.2"},{"comment":"There are several typographical issues, including 'Goddarda' in reference [3] and the phrase in Observation 3 'd_G(y3)=1, i.e., y1y3 < E(G)' where the symbol should be written as 'not in E(G)'. These should be cleaned up.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid core idea and the NP-completeness reduction is essentially sound, but the abstract's general-k claim is not supported by the proof, and the classification in Theorem 2.3 has a genuine proof gap in Observation 3. Both issues are fixable without changing the likely validity of the k=2 result, so major revision rather than rejection seems appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper is two things: a clean NP-completeness proof for k-rainbow independent domination on bipartite graphs, and an attempted improvement of the Nordhaus-Gaddum bound for γ_ri2 from n+3 to n+2 (with C5 as the only exception). The first part is solid; the second part is plausible but not established as written.\n\nWhat's new: the characterization of connected graphs with γ_ri2 = n-1 (Theorem 2.3), the extension to disconnected graphs (Theorem 2.4), and the improved upper bound for k=2 (Theorem 3.5). The NP-completeness reduction is standard but clean: attach a K_{1,k-1} star to each vertex of a bipartite graph G, and show a dominating set of size ℓ corresponds to a kRiDF of weight (k-1)(m+n)+ℓ. I checked the construction; the independence and domination conditions work, so that part deserves credit.\n\nThe problem is in Section 2, Observation 3. The proof wants to show that N_G(x) contains at most two 2-vertices. It assumes three, x1,x2,x3, sets N_G(x3)={x,y3}, and then says 'By Observation 1, d_G(y3)=1'. Observation 1 only says that every 2+-vertex lies in N_G(x); it doesn't say y3 cannot be another neighbor of x. If y3 ∈ N_G(x), the asserted nonedge y1y3 is not justified, and the constructed local 2RiDF may not be valid. This isn't a minor typo: Theorem 2.4, Lemma 3.2, and Case 1 of Theorem 3.5 all depend on this classification. The theorem may be true, but as written the proof doesn't cover that case.\n\nTwo additional issues. The abstract and conclusion claim the improved bound for all k, but the proof only handles k=2. That overclaim should be corrected. Also, the definition of kRiDF is inconsistent about whether V0 is required to be independent; the alternative definition says yes, the main definition doesn't. Worth a footnote.\n\nBottom line: the paper is an honest, incremental contribution. The NP-completeness result alone is worth having, and the Nordhaus-Gaddum improvement is likely right but needs its classification proof repaired. I'd send it to a serious referee and ask for major revision, not desk reject.","headline":"NP-completeness part is fine; the improved Nordhaus-Gaddum bound is not yet proven because a load-bearing classification proof has a gap, and the abstract overclaims to all k.","tokens_in":18178,"tokens_out":9373,"would_cite":false,"duration_ms":79497,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every graph except the 5-cycle, the 2-rainbow independent domination sum is at most $n+2$.","keywords":["k-rainbow independent domination","2-rainbow independent domination number","Nordhaus-Gaddum inequality","independent domination","graph domination","NP-completeness","bipartite graphs"],"falsifier":"Run an exact computation of $\\gamma_{\\rm ri2}$ over all connected graphs up to order about nine and look for any graph outside $\\{S_{n-1}, S^{+}_{n-1}, S(n-3,1), C_5\\}$ with $\\gamma_{\\rm ri2}(G)=|V(G)|-1$; finding one would invalidate Theorem 2.4 and the support for Theorem 3.5. Equally, an exhaustive check for any graph $G\\ncong C_5$ with $\\gamma_{\\rm ri2}(G)+\\gamma_{\\rm ri2}(\\overline{G})=n+3$ would directly refute the main theorem.","tokens_in":17126,"feed_emoji":"🎯","tokens_out":16583,"duration_ms":143437,"temperature":0.7,"pith_summary":"This paper improves a Nordhaus-Gaddum-type inequality for the 2-rainbow independent domination number: for every graph $G$ of order $n\\ge 2$ that is not the 5-cycle, $5\\le \\gamma_{\\rm ri2}(G)+\\gamma_{\\rm ri2}(\\overline{G})\\le n+2$, replacing the known upper bound $n+3$. The 5-cycle is the unique graph for which the old $n+3$ bound is needed, while stars and related double stars attain the new $n+2$ bound. The proof depends on a structural classification of connected graphs satisfying $\\gamma_{\\rm ri2}(G)=|V(G)|-1$: they are stars, stars with one added edge, certain double stars, or $C_5$, with all other components being $K_1$ or $K_2$. The paper also proves that deciding whether a graph admits a $k$-rainbow independent dominating function of a given weight is NP-complete for bipartite graphs. The result matters because this domination parameter reduces independent domination in generalized prisms to an integer labeling problem on the base graph.","feed_headline":"For every graph except C5, rainbow domination sum is at most n+2","feed_subtitle":"A one-unit improvement over the old n+3 bound, with C5 the unique exception; the recognition problem is NP-complete.","key_machinery":"The central object is a 2-rainbow independent dominating function, written as a partition $(V_0,V_1,V_2)$ of the vertex set in which $V_1$ and $V_2$ are independent sets and every vertex of $V_0$ has neighbors in both $V_1$ and $V_2$; the weight counted is $|V_1|+|V_2|$. The argument is carried by an extension lemma: a 2-rainbow independent dominating function on any induced subgraph extends to the whole graph with weight at most $|V(G)|-|V_0|$, and each of the two nonzero parts can be overcharged by at most two vertices in any extension. This converts the sought inequality into a tight case analysis of the graph induced by $V_0$, where Theorem 2.4, the classification of graphs with $\\gamma_{\\rm ri2}(G)=|V(G)|-1$, supplies the allowable structure.","core_discovery":"At the level of the main theorem, the paper claims that the sum of the 2-rainbow independent domination numbers of a graph and its complement is never larger than $n+2$ except when the graph is the 5-cycle, for which $n+3$ is achieved. To prove this, it classifies all graphs with $\\gamma_{\\rm ri2}(G)=|V(G)|-1$; the connected members of that class are exactly the stars $S_{n-1}$, the stars-plus-one-edge $S^+_{n-1}$, the double stars $S(n-3,1)$, and $C_5$, with remaining components $K_1$ or $K_2$. The proof of the bound is a contradiction argument: assuming the sum equals $n+3$, it takes a minimal 2-rainbow independent dominating function $(V_0,V_1,V_2)$ of $G$ and builds a strictly lighter one for $G$ or for the complement, using the classification to control the subgraph induced by $V_0$. The paper further establishes NP-completeness of the $k$-rainbow independent domination decision problem on bipartite graphs by reducing the bipartite domination problem to it through a star-identification construction.","pith_inferences":["The proof is $k=2$-specific, so the natural analogue for $k\\ge 3$ (for instance a bound of the form $n+k$ in place of $n+2$) is not established here; the charging argument bounding extra nonzero vertices in each of $V_1,V_2$ does not carry over unchanged.","Because the NP-completeness reduction attaches $k-1$ leaves to every vertex, the hardness statement plausibly remains true when $k$ is fixed rather than part of the input, for every fixed $k\\ge 2$; the paper states the result with $k$ as part of the input.","The short list of graphs with $\\gamma_{\\rm ri2}(G)=|V(G)|-1$ could serve as a pruning rule in search algorithms for this domination parameter, an algorithmic use the paper does not discuss.","If the classification in Theorem 2.4 is complete, the only unresolved structural task for the $n+2$ bound is equality characterization; a small counterexample, if any, would most likely be found by exhaustive computation on connected graphs of small order."],"forward_implications":["The upper bound $\\gamma_{\\rm ri2}(G)+\\gamma_{\\rm ri2}(\\overline{G})\\le n+2$ holds for every graph of order $n\\ge 2$ except $C_5$, lowering the previous bound by one for all non-exceptional graphs.","The old bound $n+3$ is sharp exactly at $C_5$, so the improved inequality cannot be extended uniformly to all graphs.","The new bound is attained: stars, stars with one added edge, and the double stars $S(n-3,1)$ satisfy $\\gamma_{\\rm ri2}(G)+\\gamma_{\\rm ri2}(\\overline{G})=|V(G)|+2$.","The decision problem for $k$-rainbow independent dominating functions of bounded weight is NP-complete for bipartite graphs, as shown by reduction from the bipartite domination problem.","Which graphs achieve the new $n+2$ bound is left open in the paper as Question 5.1."],"supporting_citations":[{"why":"Introduces $k$-rainbow independent domination, proves the baseline $n+3$ Nordhaus-Gaddum bound and Lemma 2.1, and supplies the open questions answered here.","marker":"[8]"},{"why":"Supplies the $k=1$ base case: independent domination is NP-complete for bipartite graphs.","marker":"[3]"},{"why":"Supplies the NP-complete source problem, the domination problem on bipartite graphs, used in the reduction of Theorem 4.1.","marker":"[12]"}],"fun_headline_variants":["Rainbow domination sum: n+2 for all graphs except C5","Graph-complement domination bound improved to n+2, C5 only exception","NP-complete: deciding k-rainbow independent domination","Tighter bound for graph complement domination: n+2, C5 is the outlier","Rainbow domination sum n+2 except C5; recognition NP-complete"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the $n+2$ bound rests on the claim that the only connected graphs whose 2-rainbow independent domination number is exactly one less than their vertex count are stars, stars with one added edge, certain double stars, and the 5-cycle; if that list is missing a graph, the case analysis is incomplete and the improved bound could fail.","fun_headline_variants_meta":{"raw":{"variants":["Rainbow domination sum: n+2 for all graphs except C5","Graph-complement domination bound improved to n+2, C5 only exception","NP-complete: deciding k-rainbow independent domination","Tighter bound for graph complement domination: n+2, C5 is the outlier","Rainbow domination sum n+2 except C5; recognition NP-complete"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001273,"raw_usage":{"total_tokens":5288,"prompt_tokens":1106,"completion_tokens":4182,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":722,"completion_tokens_details":{"reasoning_tokens":4084}},"tokens_in":722,"tokens_out":4182,"duration_ms":30647,"temperature":1.0,"reasoning_tokens":4084,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:16:05.873799+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exact computation of $\\gamma_{\\rm ri2}$ over all connected graphs up to order about nine and look for any graph outside $\\{S_{n-1}, S^{+}_{n-1}, S(n-3,1), C_5\\}$ with $\\gamma_{\\rm ri2}(G)=|V(G)|-1$; finding one would invalidate Theorem 2.4 and the support for Theorem 3.5. Equally, an exhaustive check for any graph $G\\ncong C_5$ with $\\gamma_{\\rm ri2}(G)+\\gamma_{\\rm ri2}(\\overline{G})=n+3$ would directly refute the main theorem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces $k$-rainbow independent domination, proves the baseline $n+3$ Nordhaus-Gaddum bound and Lemma 2.1, and supplies the open questions answered here."},{"cited_title":"Goddarda, M","cited_arxiv_id":null,"evidence_quote":"Supplies the $k=1$ base case: independent domination is NP-complete for bipartite graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the NP-complete source problem, the domination problem on bipartite graphs, used in the reduction of Theorem 4.1."}],"review_version":1}