pith. sign in

arxiv: 2606.22428 · v1 · pith:B5FXPNF6new · submitted 2026-06-21 · 🧮 math.CO

On k-limited domination: complexity and Cartesian products

Aleksandra Tepeh This is my paper

Pith reviewed 2026-06-26 10:20 UTC · model grok-4.3

classification 🧮 math.CO
keywords k-limited dominationdominating setNP-completenessCartesian productdomination numberrook graphsgrid graphshypercubes
0
0 comments X

The pith

For every fixed integer k at least 2, deciding whether a graph has a k-limited dominating set of size at most ell is NP-complete.

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

A dominating set is k-limited when each of its vertices has at most k neighbors outside the set. The paper proves that the problem of deciding whether such a set of size at most ell exists is NP-complete for any fixed k of 2 or greater. It also derives general lower and upper bounds on the k-limited domination number of Cartesian products G square H, shows the bounds are tight, and computes exact values for families including rook graphs, products of k-coronas, certain grids, prisms, and hypercubes.

Core claim

A dominating set is called k-limited if every vertex in the set has at most k neighbors outside it. The minimum cardinality of a k-limited dominating set is the k-limited domination number, denoted by gamma_k^L(G). We prove that, for every fixed integer k greater than or equal to 2, deciding whether a graph admits a k-limited dominating set of size at most ell is NP-complete. In addition, we establish general lower and upper bounds for gamma_k^L(G square H), show that both are sharp, and derive exact values for several natural families of graph products.

What carries the argument

The k-limited dominating set, which requires both that the set dominates the graph and that each member has at most k neighbors outside the set.

If this is right

  • The decision problem cannot be solved in polynomial time unless P equals NP.
  • The lower and upper bounds on gamma_k^L(G square H) are attained for some pairs of graphs.
  • Exact values of the k-limited domination number hold for rook graphs, Cartesian products of k-coronas, certain grid graphs, and several cases of prisms and hypercubes.

Where Pith is reading between the lines

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

  • The NP-completeness result suggests that similar hardness may hold for related limited-domination parameters or for other graph operations beyond Cartesian products.
  • Exact formulas for specific product families could be used to test conjectures about domination numbers in larger grid-like or network graphs.
  • The verification procedure being polynomial supports the claim that the problem is in NP, but leaves open whether the hardness proof technique extends to weighted or directed variants.

Load-bearing premise

A proposed k-limited dominating set can be verified in polynomial time by checking both the domination condition and the at-most-k external neighbors condition for each vertex in the set.

What would settle it

A polynomial-time algorithm that correctly decides the existence of a k-limited dominating set of size at most ell for some fixed k at least 2 would falsify the NP-completeness claim.

Figures

Figures reproduced from arXiv: 2606.22428 by Aleksandra Tepeh.

Figure 1
Figure 1. Figure 1: The gadget S placed between vertices vi and vj of G. precisely, for every edge vivj ∈ E(G) we add to D′ the vertices b ij and x ij t for all t ∈ [k]. In addition, we include c ij whenever vi ∈ D or vj ∈ D, and otherwise we include d ij 1 . Formally, D′ = D ∪ [ vivj∈E(G)  {b ij} ∪ {x ij t : t ∈ [k]} ∪ Z ij , where Z ij = {c ij} if vi ∈ D or vj ∈ D, and Z ij = {d ij 1 } otherwise. Each gadget contributes e… view at source ↗
Figure 2
Figure 2. Figure 2: A local view of the modification: black vertices belong to [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
read the original abstract

A dominating set is called $k$-limited if every vertex in the set has at most $k$ neighbors outside it. The minimum cardinality of a $k$-limited dominating set is the $k$-limited domination number, denoted by $\gamma_k^{\mathrm{L}}(G)$. We prove that, for every fixed integer $k\ge 2$, deciding whether a graph admits a $k$-limited dominating set of size at most $\ell$ is $\mathsf{NP}$-complete. In addition, a systematic study of $k$-limited domination in Cartesian products is initiated. In particular, we establish general lower and upper bounds for $\gamma_k^{\mathrm{L}}(G\square H)$, show that both are sharp, and derive exact values for several natural families of graph products. Among others, we obtain exact results for rook graphs, Cartesian products of $k$-coronas, certain grid graphs, and several cases involving prisms and hypercubes.

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 proves that deciding the existence of a k-limited dominating set of size at most ℓ is NP-complete for every fixed k ≥ 2. It also initiates the study of the k-limited domination number γ_k^L(G) in Cartesian products G□H by establishing general lower and upper bounds (shown to be sharp) and deriving exact values for families including rook graphs, k-coronas, certain grids, prisms, and hypercubes.

Significance. The NP-completeness result strengthens the known hardness landscape for domination variants. The product-graph results are useful because they supply both general bounds with matching constructions and exact values on concrete families; the explicit sharpness proofs and exact derivations for multiple natural products constitute a solid starting point for further work on limited domination parameters.

minor comments (3)
  1. The definition of a k-limited dominating set (every vertex in the set has at most k neighbors outside the set) should be stated explicitly in the introduction before the complexity result is announced.
  2. In the Cartesian-product section, the general lower and upper bounds should be accompanied by a short table or list of the families for which equality is attained, to improve readability.
  3. Notation: ensure that the symbol ℓ is introduced as the size bound in the decision problem statement and is used consistently in the NP-completeness theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of the manuscript. The recommendation of minor revision is noted. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central results consist of a direct NP-completeness proof (via explicit reduction for the decision problem) and independent derivations of lower/upper bounds plus exact values for Cartesian products of graphs. Membership in NP follows from a standard polynomial-time verification procedure on a certificate set S that checks domination and the k-neighbor limit via adjacency traversal; this verification is external to any fitted parameters or prior self-citations. No equations, ansatzes, or uniqueness claims reduce by construction to the paper's own inputs, and no load-bearing premise rests solely on overlapping-author citations. The derivation chain is therefore self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the newly introduced definition of a k-limited dominating set together with standard background from graph theory and complexity theory; no free parameters or invented entities are introduced.

axioms (2)
  • standard math Graphs are finite, simple, and undirected.
    Implicit foundation for all domination and product results in the abstract.
  • standard math The Cartesian product G□H has vertex set V(G)×V(H) and edges between (u,v) and (u',v') when either u=u' and v~v' or v=v' and u~u'.
    Standard definition invoked for all product bounds and exact values.

pith-pipeline@v0.9.1-grok · 5685 in / 1401 out tokens · 60508 ms · 2026-06-26T10:20:14.229806+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

19 extracted references · 13 canonical work pages

  1. [1]

    Azarija, M

    J. Azarija, M. A. Henning, S. Klavˇ zar, (Total) Domination in Prisms Electron. J. Comb., 24(1), 2017, #P1.19.https://doi.org/10.37236/6288

    work page doi:10.37236/6288 2017

  2. [2]

    Boˇ zovi´ c, G

    D. Boˇ zovi´ c, G. Radi´ c,ˇZ. Kovijani´ c-Vuki´ cevi´ c, A. Tepeh, Onk-limited domination in graphs, submitted

  3. [3]

    Breˇ sar, P

    B. Breˇ sar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klavˇ zar, D. F. Rall, Vizing’s conjecture: a survey and recent results, J. Graph Theory 69 (2012) 46–76.https://doi.org/10.1002/jgt.20565

    work page doi:10.1002/jgt.20565 2012

  4. [4]

    Chellali, T

    M. Chellali, T. W. Haynes, S. T. Hedetniemi, A. McRae, [1,2]-sets in graphs, Discrete Appl. Math. 161 (2013) 2885–2893.https://doi.org/10.1016/j.dam.2013.06.012

    work page doi:10.1016/j.dam.2013.06.012 2013

  5. [5]

    Three-level parallel J-Jacobi algorithms for Hermitian matrices

    R. Erveˇ s, A. Tepeh, Induced cycles vertex number and (1,2)-domination in cubic graphs,Appl. Math. Comput.510(2025), 129700,https://doi.org/10.1016/j.amc. 2025.129700

    work page doi:10.1016/j.amc 2025

  6. [6]

    M. H. Fakhran, A. A. Gorzin, M. A. Henning, A. Jafari and R. Touserkani, On (1,2)- domination in cubic graphs,Discrete Math.344(2021) 112546,https://doi.org/10. 1016/j.disc.2021.112546

    arXiv 2021

  7. [7]

    Favaron, M

    O. Favaron, M. A. Henning, J. Puech, D. Rautenbach, On domination and annihilation in graphs with claw-free blocks, Discrete Math. 231 (2001) 143–151.https://doi.org/ 10.1016/S0012-365X(00)00313-7

    work page doi:10.1016/s0012-365x(00)00313-7 2001

  8. [8]

    J. F. Fink, M. S. Jacobson,n-domination in graphs, in: Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk (Eds.), Graph Theory with Applications to Algo- rithms and Computer Science, Wiley, New York, 1985, pp. 283–300

    1985

  9. [9]

    M. R. Garey, D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979.https://doi.org/10. 1137/1024022

    1979

  10. [10]

    Goddard, M

    W. Goddard, M. A. Henning, A note on domination and total domination in prisms, J. Comb. Optim. 35 (2018) 14–20.https://doi.org/10.1007/s10878-017-0150-0

    work page doi:10.1007/s10878-017-0150-0 2018

  11. [11]

    Harary, M

    F. Harary, M. Livingston, Independent domination in hypercubes, Appl. Math. Lett. 6 (1993) 27–28.https://doi.org/10.1016/0893-9659(93)90027-K

    work page doi:10.1016/0893-9659(93)90027-k 1993

  12. [12]

    T. W. Haynes, S. T. Hedetniemi, M. A. Henning (Eds.), Topics in Domination in Graphs, Developments in Mathematics, Vol. 64, Springer, Cham, 2020.https://doi. org/10.1007/978-3-030-51117-3

    work page doi:10.1007/978-3-030-51117-3 2020

  13. [13]

    T. W. Haynes, S. T. Hedetniemi, M. A. Henning (Eds.), Structures of Domination in Graphs, Developments in Mathematics, Vol. 66, Springer, Cham, 2021.https: //doi.org/10.1007/978-3-030-58892-2 17

    work page doi:10.1007/978-3-030-58892-2 2021

  14. [14]

    T. W. Haynes, S. T. Hedetniemi, M. A. Henning, Domination in Graphs: Core Con- cepts, Series: Springer Monographs in Mathematics, Springer, Cham, 2023.https: //doi.org/10.1007/978-3-031-09496-5

    work page doi:10.1007/978-3-031-09496-5 2023

  15. [15]

    Ghareghani, I

    N. Ghareghani, I. Peterin, P. Sharifani, [1, k]-domination number of lexicographic prod- ucts of graphs, Bull. Malays. Math. Sci. Soc. 44 (2021) 375–392.https://doi.org/ 10.1007/s40840-020-00957-0

    work page doi:10.1007/s40840-020-00957-0 2021

  16. [16]

    Radi´ c, G

    G. Radi´ c, G. Radi´ c, A. Tepeh, (1,2)-domination of Flower snarks, submitted

  17. [17]

    Tepeh, Total domination in generalized prisms and a new domination invariant, Discuss

    A. Tepeh, Total domination in generalized prisms and a new domination invariant, Discuss. Math. Graph Theory 41 (2021) 1165–1178.https://api.semanticscholar. org/CorpusID:209476345

    2021

  18. [18]

    G. J. M. van Wee, Improved sphere bounds on the covering radius of codes. IEEE Trans. Inform. Theory 34 (1988) 237–245.https://doi.org/10.1109/18.2632

    work page doi:10.1109/18.2632 1988

  19. [19]

    Wu, J.-Y

    Y.-S. Wu, J.-Y. Chen, Improved lower bounds on the domination number of hypercubes and binary codes with covering radius one, Discrete Math. 347 (2024) 113752.https: //doi.org/10.1016/j.disc.2023.113752 18

    work page doi:10.1016/j.disc.2023.113752 2024