Article in volume
Authors:
Title:
Fault-tolerant identifying codes in special classes of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 591-611
Received: 2021-11-05 , Revised: 2022-06-01 , Accepted: 2022-06-11 , Available online: 2022-07-25 , https://doi.org/10.7151/dmgt.2465
Abstract:
A detection system, modeled in a graph, is composed of ``detectors" positioned
at a subset of vertices in order to uniquely locate an ``intruder" at any vertex.
Identifying codes use detectors that can sense the presence or absence
of an intruder within distance one. We introduce a fault-tolerant identifying
code called a redundant identifying code, which allows at most one
detector to go offline or be removed without disrupting the detection system.
In real-world applications, this would be a necessary feature, as it would allow
for maintenance on individual components without disabling the entire system.
Specifically, we prove that the problem of determining the lowest cardinality of
a redundant identifying code for an arbitrary graph is NP-hard, and we determine
the bounds on the lowest cardinality for special classes of graphs, including
trees, ladders, cylinders, and cubic graphs.
Keywords:
domination, detection system, identifying-code, fault-tolerant, redundant-identifying-code, density
References:
- D. Auger, I. Charon and O. Hudry and A. Lobstein, Watching systems in graphs: an extension of identifying codes, Discrete Appl. Math. 161 (2013) 1674–1685.
https://doi.org/10.1016/j.dam.2011.04.025 - I. Charon, O. Hudry and A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci. 290 (2003) 2109–2120.
https://doi.org/10.1016/S0304-3975(02)00536-4 - G.D. Cohen, I. Honkala, A. Lobstein and G. Zémor, On identifying codes, in: Proc. DIMACS Workshop on Codes and Association Schemes, {DIMACS Ser. Discrete Math. Theoret. Comput. Sci.} 56, (Amer. Math. Soc., Providence 2001) 97–109.
https://doi.org/10.1090/dimacs/056 - G.D. Cohen, I. Honkala, A. Lobstein and G. Zémor, Bounds for codes identifying vertices in the hexagonal grid, SIAM J. Discrete Math. 13 (2000) 492–504.
https://doi.org/10.1137/S0895480199360990 - C.J. Colbourn, P.J. Slater and L.K. Stewart, Locating-dominating sets in series-parallel networks, Congr. Numer. 56 (1987) 135–162.
- A. Cukierman and G. Yu, New bounds on the minimum density of an identifying code for the infinite hexagonal grid, Discrete Appl. Math. 161 (2013) 2910–2924.
https://doi.org/10.1016/j.dam.2013.06.002 - F. Foucaud, M.A. Henning, C. Löwenstein and T. Sasse, Locating-dominating sets in twin-free graphs, Discrete Appl. Math. 200 (2016) 52–58.
https://doi.org/10.1016/j.dam.2015.06.038 - M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979).
- D.C. Jean and S.J. Seo, Optimal error-detecting open-locating-dominating set on the infinite triangular grid, Discuss. Math. Graph Theory(2021), in press.
https://doi.org/10.7151/dmgt.2374 - M.G. Karpovsky, K. Chakrabarty and L.B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (1998) 599–611.
https://doi.org/10.1109/18.661507 - Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs (2022).
https://www.lri.fr/\%7elobstein/debutBIBidetlocdom.pdf - S.J. Seo and P.J. Slater, Open neighborhood locating-dominating sets, Australas. J. Combin. 46 (2010) 109–119.
- S.J. Seo and P.J. Slater, Fault tolerant detectors for distinguishing sets in graphs, Discuss. Math. Graph Theory 35 (2015) 797–818.
https://doi.org/10.7151/dmgt.1838 - P.J. Slater, Domination and location in acyclic graphs, Networks 17 (1987) 55–64.
https://doi.org/10.1002/net.3230170105 - P.J. Slater, Fault-tolerant locating-dominating sets, Discrete Math. 249 (2002) 179–189.
https://doi.org/10.1016/S0012-365X(01)00244-8 - P.J. Slater, A framework for faults in detectors within network monitoring systems, WSEAS Trans. Math. 12 (2013) 911–916.
Close