Fault Tolerant Detectors for Distinguishing Sets in Graphs

• Autorzy: Suk J. Seo , Peter J. Slater
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

distinguishing sets; fault tolerant detectors; redundant distinguishing open-locating-dominating set; detection distinguishing open-locating-dominating set

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 4
• Strony: 797-818

Daty

wydano

2015-11-01

otrzymano

2014-10-27

poprawiono

2015-04-07

zaakceptowano

2015-04-07

online

2015-11-10

Twórcy

autor

Suk J. Seo

• Computer Science Department Middle Tennessee State University Murfreesboro, TN 37132, USA

autor

Peter J. Slater

• Mathematical Sciences Department and Computer Science Department University of Alabama in Huntsville Huntsville, AL 35899 USA

Bibliografia

• [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[Crossref]
• [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[WoS][Crossref]
• [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[Crossref]
• [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[Crossref]
• [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[Crossref][WoS]
• [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[Crossref]
• [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[Crossref]
• [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[Crossref][WoS]
• [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[Crossref]
• [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[Crossref]
• [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[WoS][Crossref]
• [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[Crossref]
• [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[Crossref]
• [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[WoS]
• [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[Crossref]
• [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[WoS][Crossref]
• [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[Crossref][WoS]
• [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[Crossref][WoS]
• [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.[WoS]
• [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[Crossref][WoS]
• [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[Crossref]
• [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.[WoS]
• [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[Crossref]
• [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[Crossref]
• [45] P.J. Slater, Liar’s domination, Networks 54 (2009) 70-74. doi:10.1002/net.20295[Crossref]
• [46] P.J. Slater, A framework for faults in detectors within network monitoring systems, WSEAS Trans. Math. 12 (2013) 911-916.

Identyfikatory

DOI

10.7151/dmgt.1838