PreprintCC BY 4.0arXiv
On k-limited domination: complexity and Cartesian products
Abstract
A dominating set is called k-limited if every vertex in the set has at most k neighbors outside it. The minimum cardinality among all k-limited dominating sets of a graph G is the k-limited domination number, denoted by γkL(G). We prove that, for every fixed integer k≥ 2, deciding whether a graph admits a k-limited dominating set of size at most ℓ is 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 γkL(G□ H), show that both are sharp, and derive exact values for several natural families of graph products.
Related
- Grundy Total Domination and Skew Zero Forcing in Cartesian Products of Paths and Cycles
- On k-limited domination: complexity and Sierpiński graphs
- On $1$-limited and (1,2)-domination in cubic graphs
- Structural aspects of $1$-limited domination in cubic graphs
- An improved lower and upper bound of the k-limited domination number
BibTeX
@misc{tepeh2026klimited,
title = {{On $k$-limited domination: complexity and Cartesian products}},
author = {Aleksandra Tepeh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.22428},
eprint = {2606.22428},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.22428},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On k-limited domination: complexity and Cartesian products
AU - Aleksandra Tepeh
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2606.22428
UR - https://arxiv.org/abs/2606.22428
AB - A dominating set is called k-limited if every vertex in the set has at most k neighbors outside it. The minimum cardinality among all k-limited dominating sets of a graph G is the k-limited domination number, denoted by γ_k^L(G). We prove that, for every fixed integer k≥ 2, deciding whether a graph admits a k-limited dominating set of size at most ℓ is 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 γ_k^L(G□ H), show that both are sharp, and derive exact values for several natural families of graph products.
ER -