Geodesic
Fault Tolerant Detectors for Distinguishing Sets in Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 797-818.

Voir la notice de l'article provenant de la source Library of Science

For various domination-related parameters involving locating devices (distinguishing sets) that function as places from which detectors can determine information about the location of an “intruder”, several types of possible detector faults are identified. Two of these fault tolerant detector types for distinguishing sets are considered here, namely redundant distinguishing and detection distinguishing. Illustrating these concepts, we focus primarily on open-locating-dominating sets.
Keywords: distinguishing sets, fault tolerant detectors, redundant distinguishing open-locating-dominating set, detection distinguishing open-locating-dominating set 
@article{DMGT_2015_35_4_a15,
     author = {Seo, Suk J. and Slater, Peter J.},
     title = {Fault {Tolerant} {Detectors} for {Distinguishing} {Sets} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {797--818},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a15/}
}
TY  - JOUR
AU  - Seo, Suk J.
AU  - Slater, Peter J.
TI  - Fault Tolerant Detectors for Distinguishing Sets in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 797
EP  - 818
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a15/
LA  - en
ID  - DMGT_2015_35_4_a15
ER  - 
%0 Journal Article
%A Seo, Suk J.
%A Slater, Peter J.
%T Fault Tolerant Detectors for Distinguishing Sets in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 797-818
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a15/
%G en
%F DMGT_2015_35_4_a15
Seo, Suk J.; Slater, Peter J. Fault Tolerant Detectors for Distinguishing Sets in Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 797-818. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a15/

[1] Y. Ben-Haim and S. Litsyn, Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math. 19 (2005) 69-82. doi:10.1137/S0895480104444089

[2] N. Bertrand, I. Charon, O. Hudry and A. Lobstein, Identifying and locating- dominating codes on chains and cycles, European J. Combin. 25 (2004) 969-987. doi:10.1016/j.ejc.2003.12.013

[3] M. Blidia, M. Chellali, R. Lounes and F. Maffray, Characterizations of trees with unique minimum locating-dominating sets, J. Combin. Math. Combin. Comput. 76 (2011) 225-232.

[4] M. Blidia, M. Chellali, F. Maffray, J. Moncel and A. Semri, Locating-domination and identifying codes in trees, Australas. J. Combin. 39 (2007) 219-232.

[5] M. Chellali, N.J. Rad, S.J. Seo and P.J. Slater, On open neighborhood locating- dominating in graphs, Electron. J. Graph Theory Appl. 2 (2014) 87-98. doi:10.5614/ejgta.2014.2.2.1

[6] 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. doi:10.1137/S0895480199360990

[7] 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. doi:10.1016/j.dam.2013.06.002

[8] G. Exoo, V. Junnila and T. Laihonen, Locating-dominating codes in cycles, Aus- tralas. J. Combin. 49 (2011) 177-194.

[9] F. Foucaud, R. Klasing and P.J. Slater, Centroidal bases in graphs, Networks 64 (2014) 96-108. doi:10.1002/net.21560

[10] D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, Congr. Numer. 71 (1990) 153-172.

[11] F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195.

[12] T.W. Haynes, C. Sterling and P.J. Slater, Liar’s domination in ladders, Congr. Numer. 212 (2012) 45-56.

[13] M. Henning and A. Yeo, Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs, Graphs Combin. 30 (2014) 909-932. doi:10.1007/s00373-013-1311-2

[14] C. Hernando, M. Mora and I.M. Pelayo, Nordhaus-Gaddum bounds for locating domination, European J. Combin. 36 (2014) 1-6. doi:10.1016/j.ejc.2013.04.009

[15] C. Hernando, M. Mora, P.J. Slater and D.R. Wood, Fault-tolerant metric dimension of graphs, Ramanujan Math. Soc. Lect. Notes 5 (2008) 81-85.

[16] I. Honkala, An optimal locating-dominating set in the infinite triangular grid, Dis- crete Math. 306 (2006) 2670-2681. doi:10.1016/j.disc.2006.04.028

[17] I. Honkala, An optimal strongly identifying code in the infinite triangular grid, Elec- tron. J. Combin. 17 (2010) R91.

[18] I. Honkala and T. Laihonen, On locating-domination sets in infinite grids, European J. Combin. 27 (2006) 218-227. doi:10.1016/j.ejc.2004.09.002

[19] I. Honkala and T. Laihonen, On identifying codes that are robust against edge changes, Inform. and Comput. 205 (2007) 1078-1095. doi:10.1016/j.ic.2007.01.003

[20] I. Honkala, T. Laihonen and S. Ranto, On strongly identifying codes, Discrete Math. 254 (2002) 191-205. doi:10.1016/S0012-365X(01)00357-0

[21] 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. doi:10.1109/18.661507

[22] R. Kincaid, A. Oldham and G. Yu, On optimal open locating-dominating sets in infinite triangular grids, March 28 (2014) manuscript. math.CO arXiv:1403.7061v1

[23] A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs. http://www.infres.enst.fr/lobstein/debutBIBidetlocdom.pdf

[24] J. Moncel, On graphs on n vertices having an identifying code of cardinality ⌈log2(n+ 1)⌉, Discrete Appl. Math. 154 (2006) 2032-2039. doi:10.1016/j.dam.2006.03.011

[25] B.S. Panda and S. Paul, A linear time algorithm for liar’s domination problem in proper interval graphs, Inform. Process. Lett. 113 (2013) 815-822. doi:10.1016/j.ipl.2013.07.012

[26] B.S. Panda and S. Paul, Hardness results and approximation algorithm for total liar’s domination in graphs, J. Comb. Optim. 27 (2014) 643-662. doi:10.1007/s10878-012-9542-3

[27] M.L. Roden and P.J. Slater, Liars’ domination and the domination continuum, Congr. Numer. 190 (2008) 77-85.

[28] M.L. Roden and P.J. Slater, Liar’s domination in graphs, Discrete Math. 309 (2009) 5884-5890. doi:10.1016/j.disc.2008.07.019

[29] M. Roden-Bowie and P.J. Slater, Set-sized (1, 3)-domination for trees, Congr. Nu- mer. 196 (2009) 203-213.

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

[31] S.J. Seo and P.J. Slater, Open neighborhood locating-dominating in trees, Discrete Appl. Math. 159 (2011) 484-489. doi:10.1016/j.dam.2010.12.010

[32] S.J. Seo and P.J. Slater, Open neighborhood locating-domination for infinite cylin- ders, Proceedings of ACM SE (2011) 334-335. doi:10.1145/2016039.2016134

[33] S.J. Seo and P.J. Slater, Open neighborhood locating-domination for grid-like graphs, Bull. Inst. Combin. Appl. 65 (2012) 89-100.

[34] S.J. Seo and P.J. Slater,Graphical parameters for classes of tumbling block graphs, Congr. Numer. 213 (2012) 155-168.

[35] S.J. Seo and P.J. Slater, Open locating-dominating interpolation for trees, Congr. Numer. 215 (2013) 145-152.

[36] S.J. Seo and P.J. Slater, Old trees with maximum degree three, Util. Math. 94 (2014) 361-380.

[37] J.L. Sewell, Ph.D. Dissertation, in preparation.

[38] J.L. Sewell and P.J. Slater, Fault tolerant identifying codes and locating-dominating sets, in preparation.

[39] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549-559.

[40] P.J. Slater, Domination and location in graphs, National University of Singapore, Research Report 93 (1983).

[41] P.J. Slater, Dominating and location in acyclic graphs, Networks 17 (1987) 55-64. doi:10.1002/net.3230170105

[42] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988) 445-455.

[43] P.J. Slater, Locating dominating sets and locating-dominating sets, in: Graph The- ory, Combinatorics, and Applications: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs 2 (1995) 1073-1079.

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

[45] P.J. Slater, Liar’s domination, Networks 54 (2009) 70-74. doi:10.1002/net.20295

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