Notes on k-rainbow independent domination in graphs

Chanjuan Liu; Enqiang Zhu

REVIEW 3 major objections 5 minor 12 references

Notes on k-rainbow independent domination in graphs

T0 review · 3 major / 5 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 For every graph except the 5-cycle, the 2-rainbow independent domination sum is at most $n+2$.

desk verdict 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. read the letter →

arxiv 1908.01432 v1 pith:ANKUN6I6 submitted 2019-08-05 math.CO

Enqiang Zhu , Chanjuan Liu This is my paper · ORCID

classification math.CO MSC 05C6968Q17

keywords k-rainbowindependentdomination2-rainbownumberNordhaus-GadduminequalitygraphNP-completenessbipartitegraphs

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

Colleague,

This 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.

What'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.

The 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.

Two 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.

Bottom 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Abstract and Section 5] 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.
[Theorem 3.5] 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 2, Observation 3] 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.

minor comments (5)

[Abstract] 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 4, Theorem 4.1] 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.
[Lemma 3.3(3)] 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'.
[Lemma 3.2] 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)=∅.
[Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivation is a case analysis over external known bounds and classifications, with no fitted parameters or self-referential reductions.

full rationale

The paper's central improvement of the Nordhaus-Gaddum-type bound is proved by contradiction from the known upper bound n+3 of Sumenjak, Rall and Tepeh [8], which is an external published result and not derived in this paper. The classification of graphs with gamma_ri2(G)=|V(G)|-1 in Theorem 2.3 is a new structural result proved from the definition of 2RiDF and simple extension Lemma 2.2, not a restatement of an input. Lemma 3.2 uses Theorem 2.4 and constructs explicit 2RiDFs for complements, and Theorem 3.5 is a lengthy case analysis that produces explicit functions rather than appealing to the desired inequality. The NP-completeness proof gives a direct polynomial reduction from the standard domination problem, so that result is also independently grounded. The apparent flaw in Observation 3 identified in the skeptical commentary is a possible proof gap, but it is a correctness concern, not a circularity: the step 'By Observation 1, d_G(y3)=1' would be an invalid inference, not a reduction of the theorem to its own conclusion. No parameter is fitted, no prediction is renamed from an input, and the self-citations to [8] are external evidence rather than load-bearing self-support. Therefore the circularity score is 0.

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

The paper introduces no new fitted parameters or invented entities. It relies on the standard definition of k-rainbow independent domination from [8], on two theorems from [8] (Lemma 2.1 and the n+3 upper bound), and on known NP-completeness results. The most notable assumption is the intended definition of kRiDF: the paper's alternative formulation says V0 is independent, but the abstract and all proofs use the standard definition where only V1,...,Vk are independent.

assumptions (6)

domain assumption Definition of k-rainbow independent dominating function as introduced by Sumenjak, Rall and Tepeh [8].
Section 1 states the definition; the alternative partition formulation incorrectly requires V0 independent, but the abstract and proofs use the standard definition where V0 need not be independent.
domain assumption Lemma 2.1 from [8]: gamma_ri2(G)=n iff every component of G is K1 or K2, and if so gamma_ri2(complement G)=2.
Used in Section 2 and in Lemma 3.2 to derive contradictions from gamma_ri2(G)=n.
domain assumption The Nordhaus-Gaddum upper bound gamma_ri2(G)+gamma_ri2(complement G) <= n+3 for every graph of order n>=3, from [8].
Used in the proof of Theorem 3.5, where the contradiction assumption forces the sum to equal n+3.
domain assumption NP-completeness of the independent domination problem on bipartite graphs [3] and of the domination problem on bipartite graphs [12].
Used in Section 4 as the bases for the reduction to kRiDP.
standard math gamma_ri2 is additive over connected components.
Used to extend Theorem 2.3 to disconnected graphs (Theorem 2.4) and in Lemma 3.2. Follows directly from the definition but is not proved in the paper.
standard math The extension Lemma 2.2, which allows extending a kRiDF of a subgraph to the whole graph with controlled weight.
Proved in Section 2 and used throughout; the proof is correct under the standard definition (V0 not necessarily independent).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Notes on k-rainbow independent domination in graphs." pith.science (2026). https://pith.science/paper/ANKUN6I6

@misc{pith2026190801432,
  author       = {Pith},
  title        = {Pith review of: Notes on k-rainbow independent domination in graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ANKUN6I6}},
  note         = {Machine review of arXiv:1908.01432}
}

abstract

The $k$-rainbow independent domination number of a graph $G$, denoted $\gamma_{\rm rik}(G)$, is the cardinality of a smallest set consisting of two vertex-disjoint independent sets $V_1$ and $V_2$ for which every vertex in $V(G)\setminus (V_1\cup V_2)$ has neighbors in both $V_1$ and $V_2$. This domination invariant was proposed by {\v{S}}umenjak, Rall and Tepeh in (Applied Mathematics and Computation 333(15), 2018: 353-361), which allows to reduce the problem of computing the independent domination number of the generalized prism $G {\Box} K_k$ to an integer labeling problem on $G$. They proved a Nordhaus-Gaddum-type theorem: $5\leq \gamma_{\rm rik}(G)+\gamma_{\rm rik}(\overline{G})\leq n+3$ for every graph $G$ of order $n\geq 3$, where $\overline{G}$ is the complement of $G$. In this paper, we improve this result by showing that if $G$ is not isomorphic to the 5-cycle, then $5\leq \gamma_{\rm rik}(G)+\gamma_{\rm rik}(\overline{G})\leq n+2$. Moreover, we show that the problem of deciding whether a graph has a $k$-rainbow independent dominating function of a given weight is $\mathcal{NP}$-complete. Our results respond some open questions proposed by \v{S}umenjak, et al.

Figures

Figures reproduced from arXiv: 1908.01432 by the authors.

**Figure 1.** illustration of the construction from G to G 0 When k = 1, the kRiDP is equivalent to the IDP which is NP-complete when G is restricted to bipartite graphs [3]. Therefore, we assume that k ≥ 2. To show NP-hardness, we give a reduction from the domination problem (DP) for 8 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] 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]

J. A. Bondy, U. S. R. Murty, Graph theory, Springer, New York, 2008

work page 2008
[2]

T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998

1998
[3]

Goddarda, M

W. Goddarda, M. A. Henning, Independent domination in graphs: A survey and recent results 313 (2013) 839–854

work page 2013
[4]

T. P. `Avarez-Ruiz, T. Mediavilla-Gradolph, S. M. Sheikholeslami, J. C. Valenzuela-Tripodoro, I. G. Yero, On the strong roman domination number of graphs, Discrete Applied Mathematics 231 (2017) 54–59

work page 2017
[5]

Goddard, M

W. Goddard, M. A. Henning, C. A. McPillan, Semitotal domination in graphs 94 (2014) 67–81

work page 2014
[6]

E. Zhu, C. Liu, On the semitotal domination number of line graphs (2018) https: //doi.org/10.1016/j.dam.2018.06.010

work page doi:10.1016/j.dam.2018.06.010 2018
[7]

M. A. Henning, S. J ¨ager, D. Rautenbach, Relating domination, exponential domination, and porous exponential domination, Discrete Opti- mization 23 (2017) 81–92

work page 2017
[8]

T. K. ˇSumenjak, D. F. Rall, A. Tepeh, On k-rainbow independent domination in graphs, Applied Mathematics and Computation 333 (2018) 353–361

work page 2018

Show all 12 references

[9]

J. W. Grossman, F. Harary, M. Klawe, Generalized ramsey theory for graphs, xdouble stars, Discrete Mathematics 28 (1979) 247–254

1979
[10]

D. F. Manlove, On the algorithmic complexity of twelve covering and independence parameters of graphs, Discrete Applied Mathematics 91 (1999) 155–175

1999
[11]

K. S. Booth, J. H. Johnson, Dominating sets in chordal graphs 11 (1) (1982) 191–199

1982
[12]

G. J. Chang, G. L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM journal of Algebraic Discrete Methods 5 (3) (1984) 332–345. 9

1984

Pith tools

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

[1] [1]

J. A. Bondy, U. S. R. Murty, Graph theory, Springer, New York, 2008

work page 2008

[2] [2]

T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998

1998

[3] [3]

Goddarda, M

W. Goddarda, M. A. Henning, Independent domination in graphs: A survey and recent results 313 (2013) 839–854

work page 2013

[4] [4]

T. P. `Avarez-Ruiz, T. Mediavilla-Gradolph, S. M. Sheikholeslami, J. C. Valenzuela-Tripodoro, I. G. Yero, On the strong roman domination number of graphs, Discrete Applied Mathematics 231 (2017) 54–59

work page 2017

[5] [5]

Goddard, M

W. Goddard, M. A. Henning, C. A. McPillan, Semitotal domination in graphs 94 (2014) 67–81

work page 2014

[6] [6]

E. Zhu, C. Liu, On the semitotal domination number of line graphs (2018) https: //doi.org/10.1016/j.dam.2018.06.010

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

[7] [7]

M. A. Henning, S. J ¨ager, D. Rautenbach, Relating domination, exponential domination, and porous exponential domination, Discrete Opti- mization 23 (2017) 81–92

work page 2017

[8] [8]

T. K. ˇSumenjak, D. F. Rall, A. Tepeh, On k-rainbow independent domination in graphs, Applied Mathematics and Computation 333 (2018) 353–361

work page 2018