arxiv: 2604.12029 · v1 · submitted 2026-04-13 · 🧮 math.CO

Recognition: unknown

Upper bounds for double Roman domination and [k]-Roman domination of cylindrical graphs C_m Box P_n

Simon Brezovnik , Janez \v{Z}erovnik

Authors on Pith no claims yet

Pith reviewed 2026-05-10 14:48 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C69

keywords double Roman domination[k]-Roman dominationcylindrical gridsupper boundsperiodic constructionsresidue classesgraph domination

0 comments

The pith

Residue-class constructions asymptotically outperform multiple-based ones for upper bounds on double Roman domination numbers of cylindrical grids.

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

The paper derives new upper bounds for the [k]-Roman domination number of cylindrical grid graphs C_m □ P_n by combining linear periodic constructions, uniform ceiling-type labelings, and packing-based refinements. It first works out explicit comparisons among these families for the case of circumference 9, then extends the periodic constructions to all circumferences that are multiples of 3 through 9, and finally produces general bounds that depend only on the residue class of m modulo 5. For the concrete case k=2 the authors compare the two families and conclude that the residue-class bounds become asymptotically superior for all sufficiently large admissible m, while a few small exceptional cases are still better served by the tailored constructions. A sympathetic reader cares because these estimates directly limit the minimum total resource weight needed to satisfy the protection rules on any finite cylindrical network.

Core claim

The authors establish explicit upper bounds for γ_{[k]R}(C_m □ P_n) by combining linear periodic constructions for multiples of 3 to 9 with residue-class modulo 5 bounds that apply generally, and show through comparison that for k=2 the residue-class approach yields asymptotically better estimates than the multiple-based constructions for all sufficiently large admissible m, while tailored constructions remain competitive for certain small cases.

What carries the argument

Residue-class labelings modulo 5 together with linear periodic and ceiling-type assignments that assign integer labels to vertices of the cylindrical grid so that every vertex satisfies the [k]-Roman coverage condition with minimal total sum.

If this is right

Explicit comparisons among the three families of bounds are available for C_9 □ P_n and depend on the parameter k.
A single unified family of upper bounds covers every cylindrical grid whose circumference is a multiple of 3, 4, 5, 6, 7, 8 or 9.
General upper bounds that depend only on the residue of m modulo 5 hold for every cylindrical grid.
For double Roman domination the residue-class construction is asymptotically superior to the multiple-based one for all sufficiently large admissible m.

Where Pith is reading between the lines

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

For very large grids the optimal labeling pattern is expected to settle into a periodic structure governed by the residue class modulo 5.
The same labeling techniques could be tested on toroidal grids or other periodic lattices to obtain analogous bounds.
The exceptional small-m cases may require separate exhaustive search or integer programming to determine whether the upper bounds are tight.

Load-bearing premise

The periodic labelings and ceiling-type assignments achieve the stated coverage counts for every residue class of m modulo 5 and for every multiple of 3 through 9 without hidden overlaps or uncovered vertices.

What would settle it

A vertex labeling of some C_m □ P_n with m large and m congruent to 1 modulo 5 whose total weight is strictly smaller than the residue-class upper bound while still satisfying the double Roman condition on every vertex.

Figures

Figures reproduced from arXiv: 2604.12029 by Janez \v{Z}erovnik, Simon Brezovnik.

**Figure 1.** Figure 1: Packing pattern in C9✷Pn. The fibres follow a periodic pattern, with a cyclic shift along C9. We now state an upper bound for γ[k]R(C9✷Pn) that depends on the packing number of this graph [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

**Figure 2.** Figure 2: Best bound among Bounds (3), (5), and (7) for n = 4, . . . , 20 and k = 1, . . . , 27 (with the gap between k = 2 and k = 12). n k 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 35 36 37 38 39 40 41 42 43 44 45 Bound (3) Bound (5) Bound (7) [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Best bound among Bounds (3), (5), and (7) for n = 4, . . . , 20 and k = 35, . . . , 45 for C9✷Pn. typically prevailing for larger values of n, while the packing-based construction may yield improvements for smaller values of n [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

read the original abstract

Roman-type domination parameters form an important class of graph invariants that model protection and resource allocation problems on networks. Among them, $[k]$-Roman domination provides a unified framework that generalizes Roman, double Roman, and higher-order variants. In this paper we investigate the $[k]$-Roman domination number of cylindrical grids $C_m\Box P_n$ and derive several new constructive upper bounds. Our approach combines three complementary techniques: linear periodic constructions, uniform ceiling-type labelings, and packing-based refinements. We first analyze the case $C_9\Box P_n$, where these three families of bounds can be compared explicitly and their relative efficiency is shown to depend on the parameter $k$. We then extend the linear constructions to cylindrical grids whose circumference is a multiple of one of the values $3,\dots,9$, obtaining a unified family of upper bounds for $C_{rt}\Box P_n$. Motivated by the asymptotic behavior of these estimates, we further derive general upper bounds depending only on the residue class of $m$ modulo $5$, which apply to all cylindrical grids. As a consequence, we obtain explicit estimates for the double Roman domination number $\gamma_{[2]R}(C_m\Box P_n)$ and compare the resulting multiple-based constructions with the residue-class bounds. This comparison shows that the residue-class construction becomes asymptotically superior for all sufficiently large admissible circumferences, while several exceptional small cases remain better covered by tailored constructions.

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.

Desk Editor's Note private letter to a colleague

The paper gives new explicit upper bounds on [k]-Roman domination for cylindrical grids via residue-class labelings that are asymptotically better than multiple-based ones for large m, once the constructions are verified.

read the letter

The main point is that this work supplies concrete upper bounds for the double Roman domination number and more general [k]-Roman numbers on C_m □ P_n. The authors develop periodic labelings for m multiples of 3 through 9, then shift to residue classes modulo 5 that apply to all m. They show the residue-class versions eventually outperform the earlier multiple-based bounds for large enough circumference, with a few small cases handled by special constructions. They also compare three techniques explicitly on the C_9 case for varying k.

Referee Report

2 major / 1 minor

Summary. The paper derives constructive upper bounds on the [k]-Roman domination number of cylindrical grids C_m □ P_n. It compares three families of constructions (linear periodic labelings, uniform ceiling assignments, and packing refinements) first on C_9 □ P_n, then extends the periodic constructions to circumferences that are multiples of 3 through 9, and finally obtains general residue-class bounds depending only on m mod 5. For the special case k=2 the paper compares the multiple-based and residue-class families and concludes that the latter become asymptotically superior for all sufficiently large admissible m, while a few small exceptional cases remain better handled by tailored constructions.

Significance. If the labelings are valid, the work supplies explicit, computable upper bounds on a family of domination parameters that model resource allocation on grid-like networks. The asymptotic comparison between construction families is a concrete contribution that clarifies which method is preferable for large m. The constructive nature of the bounds also makes them directly usable for further algorithmic or extremal work on cylindrical grids.

major comments (2)

[general residue-class bounds (after the C_9 analysis)] The central upper-bound claims rest on periodic labelings and ceiling-type assignments for each residue class of m modulo 5. The manuscript must explicitly verify, for every such class, that the assigned labels produce a valid [2]-Roman dominating function (i.e., every vertex v satisfies the closed-neighborhood sum condition) and that the total weight matches the stated formula; any uncovered vertex or neighborhood sum below threshold would invalidate both the bound and the asymptotic superiority statement.
[comparison of multiple-based and residue-class bounds for γ_{[2]R}] The headline comparison that residue-class constructions eventually dominate the multiple-based ones for large admissible m presupposes that the mod-5 labelings remain valid for arbitrary n. The paper should supply a uniform argument (or at least a representative case for each residue) showing that the periodic pattern plus ceiling assignments cover the entire cylinder without local deficiencies.

minor comments (1)

Notation for the [k]-Roman function and the precise definition of the weight should be restated once at the beginning of the constructive sections to avoid ambiguity when comparing different families.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and for identifying points where our constructions require more explicit validation. We will revise the manuscript to strengthen the presentation of the residue-class bounds and their validity.

read point-by-point responses

Referee: The central upper-bound claims rest on periodic labelings and ceiling-type assignments for each residue class of m modulo 5. The manuscript must explicitly verify, for every such class, that the assigned labels produce a valid [2]-Roman dominating function (i.e., every vertex v satisfies the closed-neighborhood sum condition) and that the total weight matches the stated formula; any uncovered vertex or neighborhood sum below threshold would invalidate both the bound and the asymptotic superiority statement.

Authors: We agree that explicit verification for each residue class is essential. In the revised version we will add a new subsection (following the C_9 analysis) that lists the precise label assignments for m ≡ r mod 5 (r = 0,1,2,3,4), verifies the closed-neighborhood sum condition vertex-by-vertex for a representative period, and confirms that the total weight equals the claimed formula. These checks will be performed for the [2]-Roman case and will directly support the asymptotic comparison. revision: yes
Referee: The headline comparison that residue-class constructions eventually dominate the multiple-based ones for large admissible m presupposes that the mod-5 labelings remain valid for arbitrary n. The paper should supply a uniform argument (or at least a representative case for each residue) showing that the periodic pattern plus ceiling assignments cover the entire cylinder without local deficiencies.

Authors: We accept the need for a uniform argument. The revised manuscript will include a general lemma establishing that the periodic pattern along the path direction, combined with the ceiling adjustments at the ends, produces a valid [2]-Roman dominating function for every n. The proof proceeds by showing that interior periods satisfy the sum condition by construction and that the boundary layers are covered by the ceiling rule; we will illustrate the argument with one representative residue class and note that the remaining classes follow identically. revision: yes

Circularity Check

0 steps flagged

No circularity: upper bounds from explicit constructive labelings

full rationale

The paper obtains upper bounds on γ_{[k]R}(C_m □ P_n) and γ_{[2]R}(C_m □ P_n) via three families of explicit constructions: linear periodic labelings for circumferences that are multiples of 3–9, uniform ceiling-type assignments, and residue-class labelings modulo 5. These are presented as independent combinatorial rules that produce valid [k]-Roman dominating functions whose weights serve as upper bounds; the subsequent comparisons (including asymptotic superiority of residue-class bounds) are direct calculations on the weights of these constructions. No equation reduces a claimed bound to a fitted parameter, self-definition, or load-bearing self-citation; the derivations remain self-contained combinatorial arguments.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard definitions of [k]-Roman domination and graph products; no new free parameters, invented entities, or non-standard axioms are introduced beyond the choice of residue classes for the constructions.

axioms (2)

standard math Standard definition and coverage rules for [k]-Roman domination on graphs
The paper applies the established definition of [k]-Roman domination without modification.
standard math C_m □ P_n is the Cartesian product of cycle and path graphs
The graph class is defined via the standard Cartesian product operation.

pith-pipeline@v0.9.0 · 5577 in / 1453 out tokens · 42970 ms · 2026-05-10T14:48:51.525083+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 9 canonical work pages

[1]

Triple Roman domination in graphs

Abdollahzadeh Ahangar, H., ´Alvarez, M., Chellali, M., Sheikholeslami, S., Valenzuela-Tripodoro, J., 2021. Triple Roman domination in graphs. Applied Mathematics and Computation 391, 125444. URL:https://www.sciencedirect.com/science/article/pii/S0096300320304057, doi:https: //doi.org/10.1016/j.amc.2020.125444

work page doi:10.1016/j.amc.2020.125444 2021
[2]

Computing the domination number of grid graphs

Alanko, S., Crevals, S., Isopoussu, A., Ostergard, P., Pettersson, V., 2011). Computing the domination number of grid graphs. The Electronic Journal of Combinatorics 18

2011
[3]

Double Roman domination

Beeler, R.A., Haynes, T.W., Hedetniemi, S.T., 2016. Double Roman domination. Discrete Ap- plied Mathematics 211, 23–29. URL:https://www.sciencedirect.com/science/article/pii/ S0166218X1630155X, doi:https://doi.org/10.1016/j.dam.2016.03.017

work page doi:10.1016/j.dam.2016.03.017 2016
[4]

Further results on [k]-Roman domination on cylindrical grids Cm□Pn

Brezovnik, S., ˇZerovnik, J., 2026a. Further results on [k]-Roman domination on cylindrical grids Cm□Pn. submittedarXiv:2603.25191

work page arXiv
[5]

[k]-Roman domination on cylindrical gridsC m□Pn

Brezovnik, S., ˇZerovnik, J., 2026b. [k]-Roman domination on cylindrical gridsC m□Pn. submitted arXiv:2603.02831

work page arXiv
[6]

Domination numbers of grid graphs

Chang, T.Y., 1992. Domination numbers of grid graphs. Ph.D. thesis, Dept. of Mathematics, University of South Florida

1992
[7]

Varieties of Roman domination II

Chellali, M., Jafari Rad, N., Sheikholeslami, S.M., Volkmann, L., 2020. Varieties of Roman domination II. AKCE International Journal of Graphs and Combinatorics 17, 966–984. doi:https: //doi.org/10.1016/j.akcej.2019.12.001

work page doi:10.1016/j.akcej.2019.12.001 2020
[8]

Varieties of Roman domination, in: Haynes, T.W., Hedetniemi, S.T., Henning, M.A

Chellali, M., Jafari Rad, N., Sheikholeslami, S.M., Volkmann, L., 2021. Varieties of Roman domination, in: Haynes, T.W., Hedetniemi, S.T., Henning, M.A. (Eds.), Structures of Domination in Graphs. Springer, Cham. volume 66 ofDevelopments in Mathematics, pp. 273–307. doi:10. 1007/978-3-030-58892-2_10

2021
[9]

Roman domination in graphs

Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T., 2004. Roman domination in graphs. Discrete Mathematics 278, 11–22. doi:10.1016/j.disc.2003.06.002. 18 BREZOVNIK AND ˇZEROVNIK

work page doi:10.1016/j.disc.2003.06.002 2004
[10]

Computers and Intractability: A Guide to the Theory of NP-Completeness

Garey, M.R., Johnson, D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA

1979
[11]

Fundamentals of Domination in Graphs

Haynes, T., Hedetniemi, S., Slater, P., 1998. Fundamentals of Domination in Graphs. 1st ed. ed., CRC Press. doi:https://doi.org/10.1201/9781482246582

work page doi:10.1201/9781482246582 1998
[12]

Product Graphs: Structure and Recognition

Imrich, W., Klavzar, S., 2000. Product Graphs: Structure and Recognition. Wiley-Interscience, New York

2000
[13]

Bolin, A

Khalili, N., Amjadi, J., Chellali, M., Sheikholeslami, S.M., 2023. On [k]-Roman domination in graphs. AKCE International Journal of Graphs and Combinatorics 20, 291–299. doi:10.1080/ 09728600.2023.2241531

work page arXiv 2023
[14]

A note on the domination number of the Cartesian products of paths and cycles

Pavliˇ c, P.,ˇZerovnik, J., 2013. A note on the domination number of the Cartesian products of paths and cycles. Kragujevac Journal of Mathematics 37, 275––285

2013
[15]

Lappas, and Manolis N

Valenzuela-Tripodoro, J.C., Mateos-Camacho, M.A., Cera, M., et al., 2023. The [k]-multiple Roman domination in graphs. Research Square URL:https://doi.org/10.21203/rs.3. rs-2889100/v1, doi:10.21203/rs.3.rs-2889100/v1. preprint, Version 1. Appendix A 20 BREZOVNIK AND ˇZEROVNIK UPPER BOUNDS FOR DOUBLE ROMAN DOMINATION AND [k]-ROMAN DOMINATION OF CYLINDRICAL...

work page doi:10.21203/rs.3 2023