On $1$-limited and $(1,2)$-domination in cubic graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.01796
curl -X POST /api/v1/records/arxiv/2610.01796/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.01796/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'