| Autor: |
Jean, Devin C., Seo, Suk J. |
| Předmět: |
|
| Zdroj: |
Discrete Mathematics, Algorithms & Applications; Feb2023, Vol. 15 Issue 2, p1-17, 17p |
| Abstrakt: |
A locating-dominating set is a subset of vertices representing "detectors" in a graph G which can locate an "intruder" given that each detector covers its closed neighborhood and can distinguish its own location from its neighbors. We explore a fault-tolerant variant of locating-dominating sets, called error-detecting locating-dominating (DET:LD) sets, which can tolerate one false negative. The concept of DET:LD sets was originally introduced in 2002, along with several properties in various classes of graphs; we extend this work by fully characterizing DET:LD sets for general graphs and establishing existence criteria. We prove that the problem of determining the minimum density of a DET:LD set in arbitrary graphs is NP-complete. Additionally, we determine that the minimum density in cubic graphs is at least 3 5 , and we show an infinite family of cubic graphs achieving this density. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
