Geodesic
Fault-tolerant identifying codes in special classes of graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 591-611 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A detection system, modeled in a graph, is composed of “detectors quot; positioned at a subset of vertices in order to uniquely locate an “intruder quot; 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 
@article{DMGT_2024_44_2_a9,
     author = {Jean, Devin C. and Seo, Suk J.},
     title = {Fault-tolerant identifying codes in special classes of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {591--611},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a9/}
}
TY  - JOUR
AU  - Jean, Devin C.
AU  - Seo, Suk J.
TI  - Fault-tolerant identifying codes in special classes of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 591
EP  - 611
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a9/
LA  - en
ID  - DMGT_2024_44_2_a9
ER  - 
%0 Journal Article
%A Jean, Devin C.
%A Seo, Suk J.
%T Fault-tolerant identifying codes in special classes of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 591-611
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a9/
%G en
%F DMGT_2024_44_2_a9
Jean, Devin C.; Seo, Suk J. Fault-tolerant identifying codes in special classes of graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 591-611. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a9/

[1] 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

[2] 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

[3] 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

[4] 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

[5] C.J. Colbourn, P.J. Slater and L.K. Stewart, Locating-dominating sets in series-parallel networks, Congr. Numer. 56 (1987) 135–162.

[6] 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

[7] 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

[8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979).

[9] 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

[10] 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

[11] Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs (2022). https://www.lri.fr/\%7elobstein/debutBIBidetlocdom.pdf

[12] S.J. Seo and P.J. Slater, Open neighborhood locating-dominating sets, Australas. J. Combin. 46 (2010) 109–119.

[13] 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

[14] P.J. Slater, Domination and location in acyclic graphs, Networks 17 (1987) 55–64. https://doi.org/10.1002/net.3230170105

[15] P.J. Slater, Fault-tolerant locating-dominating sets, Discrete Math. 249 (2002) 179–189. https://doi.org/10.1016/S0012-365X(01)00244-8

[16] P.J. Slater, A framework for faults in detectors within network monitoring systems, WSEAS Trans. Math. 12 (2013) 911–916.