Fault Tolerant Detectors for Distinguishing Sets in Graphs

Suk J. Seo ; Peter J. Slater

Discussiones Mathematicae Graph Theory, Tome 35 (2015), p. 797-818 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2015-01-01

Zbl 1327.05266

EUDML-ID : urn:eudml:doc:276020

Bibliographie

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

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

[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. | Zbl 1244.05164

[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. | Zbl 1136.05049

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

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

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

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

[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. | Zbl 0691.05043

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

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

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

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

[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. | Zbl 1170.05306

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

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

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

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

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

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

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

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

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

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

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

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

[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. | Zbl 1278.05177

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

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

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

[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. | Zbl 0656.05057

[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. | Zbl 0846.05047

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

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