pith. sign in

arxiv: 1907.08430 · v1 · pith:R2QQTTFTnew · submitted 2019-07-19 · 🧮 math.CO

On k-rainbow domination in regular graphs

Bo\v{s}tjan Kuzman This is my paper

Pith reviewed 2026-05-24 19:09 UTC · model grok-4.3

classification 🧮 math.CO
keywords k-rainbow dominationregular graphsdomination numberlower boundCayley graphscubic graphsabelian groups
0
0 comments X

The pith

For a d-regular graph on n vertices the k-rainbow domination number is at least ceil(kn/2d) whenever d ≤ k ≤ 2d.

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

The paper proves a lower bound on the k-rainbow domination number for regular graphs. In a d-regular graph on n vertices, when the parameter k lies between d and 2d inclusive, this number cannot be smaller than the ceiling of kn divided by 2d. The proof rests on a counting argument that tallies the color assignments required from a minimum k-rainbow dominating set. The paper also supplies necessary conditions for equality to hold, exhibits examples that meet the bound, and uses the bound to compute exact values for every cubic Cayley graph on an abelian group.

Core claim

We prove that the k-rainbow domination number γ_rk(G) of a d-regular graph for d≤k≤2d is bounded below by ⌈kn/2d⌉, where n is the order of a graph. We determine necessary conditions for regular graphs to attain this bound and find several examples. As an application, we determine exact k-rainbow domination numbers for all cubic Cayley graphs over abelian groups.

What carries the argument

A double-counting argument on the total number of distinct color incidences delivered to non-support vertices by a k-rainbow dominating function in a d-regular graph.

If this is right

  • Equality holds only when the color-incidence count saturates every available neighbor contribution.
  • Exact k-rainbow domination numbers are obtained for the infinite family of all cubic Cayley graphs over abelian groups.
  • The bound supplies a uniform estimate that applies uniformly across all regular graphs of a given degree and order in the stated k-range.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same counting technique might yield analogous ceilings when the graph is only nearly regular, with maximum and minimum degrees differing by a small constant.
  • The bound could be used to test conjectures about the relation between rainbow domination and ordinary domination numbers in regular graphs.
  • It remains open whether a similar linear lower bound continues to hold when k falls outside the interval [d,2d].

Load-bearing premise

The graph must be exactly d-regular and k must lie between d and 2d so that each non-support vertex demands exactly k colors while each vertex has exactly d possible neighbor contributions.

What would settle it

Any single d-regular graph on n vertices with d ≤ k ≤ 2d whose minimum k-rainbow dominating set has size strictly less than ceil(kn/2d).

Figures

Figures reproduced from arXiv: 1907.08430 by Bo\v{s}tjan Kuzman.

Figure 1
Figure 1. Figure 1: Franklin graph is 3-regular and bipartite with [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two 4-RDR graphs, the wreath graph C4[2K1] and the tesseract Q4, with indicated values of their γr4-functions. • Question 1: Are there any d-RDR graphs that are not obtained as Cayley graphs over some abelian group? • Question 2: More generaly, are there any d-RDR graphs that are not vertex transitive? 6 Acknowledgments This work is supported in part by the Slovenian Research Agency (ARRS), research progra… view at source ↗
read the original abstract

The $k$-rainbow domination problem is studied for regular graphs. We prove that the $k$-rainbow domination number $\gamma_{rk}(G)$ of a $d$-regular graph for $d\leq k\leq 2d$ is bounded below by $\displaystyle{\left\lceil kn/2d\right\rceil}$, where $n$ is the order of a graph. We determine necessary conditions for regular graphs to attain this bound and find several examples. As an application, we determine exact $k$-rainbow domination numbers for all cubic Cayley graphs over abelian groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper establishes a lower bound γ_rk(G) ≥ ⌈k n / (2d)⌉ on the k-rainbow domination number of any d-regular graph G when d ≤ k ≤ 2d. It derives necessary conditions for equality, exhibits several attaining graphs, and applies the bound to compute exact values of γ_rk for every cubic Cayley graph on an abelian group.

Significance. The counting argument yields a simple, closed-form lower bound that is attained by explicit constructions; the application to an infinite family of cubic graphs demonstrates concrete utility. The result is internally consistent with the definition of k-rainbow domination and the regularity hypothesis.

minor comments (3)
  1. [§2] §2, after Definition 2.1: the phrase 'a vertex v is dominated by color i' is used before the formal definition of the function f; a forward reference or inline clarification would prevent momentary ambiguity.
  2. [Theorem 3.2] Theorem 3.2: the equality case is stated for connected graphs, yet the proof sketch in the preceding paragraph applies verbatim to disconnected graphs; either extend the statement or add a parenthetical remark.
  3. [Table 1] Table 1: the column header 'Attains bound?' should be aligned with the data rows; the current formatting makes the last two entries hard to read at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, the accurate summary of our results, and the recommendation to accept. No major comments were provided for us to address.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The central result is a lower bound γ_rk(G) ≥ ⌈kn/2d⌉ obtained via direct double-counting on label assignments in a d-regular graph (d ≤ k ≤ 2d). The argument starts from the standard definition of k-rainbow domination and the handshaking lemma implied by regularity; neither the bound nor any intermediate quantity is defined in terms of itself, fitted to data, or justified solely by prior self-citation. No equations reduce to the target expression by construction, and the paper supplies explicit constructions showing the bound is tight rather than tautological. The derivation is therefore self-contained against the given assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no free parameters, invented entities, or non-standard axioms are visible. The result rests on the ordinary definition of k-rainbow domination and the regularity assumption.

axioms (1)
  • standard math Standard definitions and counting properties of graphs and k-rainbow domination
    The bound is obtained by double counting assignments of colors to neighbors; this uses only the usual axioms of graph theory.

pith-pipeline@v0.9.0 · 5612 in / 1313 out tokens · 33727 ms · 2026-05-24T19:09:28.045471+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    N. Bray, E. W. Weisstein, Domination Number, from MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/DominationNumber.html

    work page

  2. [2]

    Breˇ sar, M.A

    B. Breˇ sar, M.A. Henning, D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008), 213–225

    work page 2008

  3. [3]

    Breˇ sar, T

    B. Breˇ sar, T. KranerˇSumenjak, On 2-rainbow domination in graphs, Discrete Applied Mathematics 155 (2007), 2394 – 2400

    work page 2007

  4. [4]

    G. J. Chang, J. Wu, X. Zhu, Rainbow domination on trees, Discrete Applied Mathematics, Volume 158 (2010), 8 – 12

    work page 2010

  5. [5]

    Fujita, M

    S. Fujita, M. Furuya, C. Magnant, General Bounds on Rainbow Domination Numbers, Graphs and Combinatorics 31 (2015) 601 – 613

    work page 2015

  6. [6]

    Furuya, M Koyanagi, M

    M. Furuya, M Koyanagi, M. Yokota, Upper bound on 3-rainbow domination in graphs with minimum degree 2, Discrete Optimization 29 (2018), 45–76

    work page 2018

  7. [7]

    Hartnell, D.F

    B. Hartnell, D.F. Rall, On dominating the Cartesian product of a graph and K2, Discuss. Math. Graph Theory 24 (2004) 389–402

    work page 2004

  8. [8]

    Kraner ˇSumenjak, D

    T. Kraner ˇSumenjak, D. F. Rall, A. Tepeh, Rainbow domination in the lexicographic product of graphs, Discrete Applied Mathematics 161 (2013), 2133 – 2141

    work page 2013

  9. [9]

    Z. Shao, M. Liang, C. Yin, X.Xu, P. Pavliˇ c, J.ˇZerovnik, On rainbow domination numbers of graphs, Information Sciences 254 (2014), 225 – 234

    work page 2014

  10. [10]

    Z. Shao, H. Jiang, P. Wu, S. Wang, J. ˇZerovnik, X. Zhang, J.B. Liu, On 2-rainbow domination of generalized Petersen graphs, Discrete Applied Mathematics 257 (2019), 370 – 384. 10

    work page 2019

  11. [11]

    Stepien, A

    Z. Stepien, A. Szymaszkiewicz, L. Szymaszkiewicz, M. Zwierzchowski, 2-Rainbow domination num- ber of Cn□C5, Discrete Appl. Math., 170 (2014), 113 – 116

    work page 2014

  12. [12]

    Math., 161 (2013), 2178 – 2188

    Wang Y., Wu K., A tight upper bound for 2-rainbow domination in generalized Petersen graphs, Discrete Appl. Math., 161 (2013), 2178 – 2188. 11

    work page 2013