{"id":"arxiv/2610.01584","url":"https://arxiv.org/abs/2610.01584","tags":["math.CO"],"score":0,"title":"On $k$-limited domination: complexity and Sierpiński graphs","domain":"math.CO","source":"arxiv","authors":["Dragana Božović"],"reviews":0,"subject":"math.CO","summary":"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 $\\mathsf{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 $\\mathsf{NP}$-complete even when restricted to planar graphs. In addition, we study the $k$-limited…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}