On $1$-limited and (1,2)-domination in cubic graphs

@misc{radic20261limited,
  title = {{On $1$-limited and $(1,2)$-domination in cubic graphs}},
  author = {Goran Radić and Aleksandra Tepeh},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01796},
  eprint = {2610.01796},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01796},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - On $1$-limited and (1,2)-domination in cubic graphs
AU  - Goran Radić
AU  - Aleksandra Tepeh
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.01796
UR  - https://arxiv.org/abs/2610.01796
AB  - 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 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 number of the entire Goldberg family. This provides a further infinite family of cubic graphs supporting several open conjectures and proposed bounds concerning (1,2)-domination and induced cycles.
ER  -