The complexity of minimum-density locating-dominating set in infinite periodic graphs
A dominating set $S$ of a graph $G$ is a locating-dominating set (LDS) if, for each pair of distinct vertices not in~$S$, their neighbourhoods in $S$ are distinct. Finding a minimum-cardinality LDS in finite graphs is a well-known NP-hard problem. On infinite graphs, this problem naturally generalises to finding an LDS of minimum density. While density bounds have been widely studied for specific infinite regular grids, no computational complexity results exist for infinite graphs. We prove that the minimum-density LDS problem in infinite $\mathbb{Z}$-periodic graphs with a finite period is…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.02882
curl -X POST /api/v1/records/arxiv/2608.02882/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02882/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'