Fault-tolerant Locating-Dominating Sets on the Infinite King Grid
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910753648279552 |
|---|---|
| author | Jean, Devin Seo, Suk |
| author_facet | Jean, Devin Seo, Suk |
| contents | Let $G$ be a graph of a network system with vertices, $V(G)$, representing physical locations and edges, $E(G)$, representing informational connectivity. A \emph{locating-dominating (LD)} set $S \subseteq V(G)$ is a subset of vertices representing detectors capable of sensing an "intruder" at precisely their location or somewhere in their open-neighborhood -- an LD set must be capable of locating an intruder anywhere in the graph. We explore three types of fault-tolerant LD sets: \emph{redundant LD} sets, which allow a detector to be removed, \emph{error-detecting LD} sets, which allow at most one false negative, and \emph{error-correcting LD} sets, which allow at most one error (false positive or negative). In particular, we determine lower and upper bounds for the minimum density of these three fault-tolerant locating-dominating sets in the \emph{infinite king grid}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_09399 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Fault-tolerant Locating-Dominating Sets on the Infinite King Grid Jean, Devin Seo, Suk Combinatorics Discrete Mathematics 05C69 Let $G$ be a graph of a network system with vertices, $V(G)$, representing physical locations and edges, $E(G)$, representing informational connectivity. A \emph{locating-dominating (LD)} set $S \subseteq V(G)$ is a subset of vertices representing detectors capable of sensing an "intruder" at precisely their location or somewhere in their open-neighborhood -- an LD set must be capable of locating an intruder anywhere in the graph. We explore three types of fault-tolerant LD sets: \emph{redundant LD} sets, which allow a detector to be removed, \emph{error-detecting LD} sets, which allow at most one false negative, and \emph{error-correcting LD} sets, which allow at most one error (false positive or negative). In particular, we determine lower and upper bounds for the minimum density of these three fault-tolerant locating-dominating sets in the \emph{infinite king grid}. |
| title | Fault-tolerant Locating-Dominating Sets on the Infinite King Grid |
| topic | Combinatorics Discrete Mathematics 05C69 |
| url | https://arxiv.org/abs/2201.09399 |