PreprintarXiv licencearXiv
On k-limited domination: complexity and Sierpiński graphs
Abstract
A dominating set D of a graph G is called k-limited if every vertex of D has at most k neighbors outside D. The minimum cardinality among all k-limited dominating sets of G is the k-limited domination number, denoted by γkL(G). In this paper, we prove that the $1$-Limited Dominating Set problem is NP-complete, answering an open question posed in the literature. We further show that, for every positive integer k, the k-Limited Dominating Set problem is NP-complete even when restricted to planar graphs. In addition, we study the k-limited domination number of Sierpiński graphs. We determine the exact value of γ1L(S(n,m)) for all integers n≥ 1 and m≥ 2, and obtain the k-limited domination number for the planar family S(n,3).
Related
- Secure Domination in Odd-order Sierpinski Graphs
- On k-limited domination: complexity and Cartesian products
- On $1$-limited and (1,2)-domination in cubic graphs
- Structural aspects of $1$-limited domination in cubic graphs
- The parameterised complexity of generalised temporal domination on temporal graphs with modular structure
BibTeX
@misc{bozovic2026klimited,
title = {{On $k$-limited domination: complexity and Sierpiński graphs}},
author = {Dragana Božović},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01584},
eprint = {2610.01584},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01584},
}
RIS
TY - UNPB
TI - On k-limited domination: complexity and Sierpiński graphs
AU - Dragana Božović
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01584
UR - https://arxiv.org/abs/2610.01584
AB - A dominating set D of a graph G is called k-limited if every vertex of D has at most k neighbors outside D. The minimum cardinality among all k-limited dominating sets of G is the k-limited domination number, denoted by γ_k^L(G). In this paper, we prove that the $1$-Limited Dominating Set problem is NP-complete, answering an open question posed in the literature. We further show that, for every positive integer k, the k-Limited Dominating Set problem is NP-complete even when restricted to planar graphs. In addition, we study the k-limited domination number of Sierpiński graphs. We determine the exact value of γ_1^L(S(n,m)) for all integers n≥ 1 and m≥ 2, and obtain the k-limited domination number for the planar family S(n,3).
ER -