{"id":"arxiv/2610.01796","url":"https://arxiv.org/abs/2610.01796","tags":["math.CO"],"score":0,"title":"On $1$-limited and $(1,2)$-domination in cubic graphs","domain":"math.CO","source":"arxiv","authors":["Goran Radić","Aleksandra Tepeh"],"reviews":0,"subject":"math.CO","summary":"A dominating set $D$ of a graph is called $1$-limited if every vertex of $D$ has at most one neighbor outside $D$, while a $(1,2)$-dominating set is a dominating set in which every vertex of the set has at least two neighbors within the set. These two notions coincide on cubic graphs. We prove that the decision problem 1-Limited Dominating Set is $\\mathsf{NP}$-complete even when restricted to $2$-connected planar cubic graphs, thereby completing the known complexity results for $k$-Limited Dominating Set for all fixed positive integers $k$. We also determine the exact $1$-limited domination…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}