Fault Tolerant Detectors for Distinguishing Sets in Graphs

Suk J. Seo; Peter J. Slater

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 797-818
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Suk J. Seo, and Peter J. Slater. "Fault Tolerant Detectors for Distinguishing Sets in Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 797-818. <http://eudml.org/doc/276020>.

@article{SukJ2015,
abstract = {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.},
author = {Suk J. Seo, Peter J. Slater},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distinguishing sets; fault tolerant detectors; redundant distinguishing open-locating-dominating set; detection distinguishing open-locating-dominating set},
language = {eng},
number = {4},
pages = {797-818},
title = {Fault Tolerant Detectors for Distinguishing Sets in Graphs},
url = {http://eudml.org/doc/276020},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Suk J. Seo
AU - Peter J. Slater
TI - Fault Tolerant Detectors for Distinguishing Sets in Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 797
EP - 818
AB - 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.
LA - eng
KW - distinguishing sets; fault tolerant detectors; redundant distinguishing open-locating-dominating set; detection distinguishing open-locating-dominating set
UR - http://eudml.org/doc/276020
ER -

References

top
  1. [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] Zbl1085.94026
  2. [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] Zbl1053.05095
  3. [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. Zbl1244.05164
  4. [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. Zbl1136.05049
  5. [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] Zbl1306.05178
  6. [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] Zbl0961.05036
  7. [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] Zbl1287.05065
  8. [8] G. Exoo, V. Junnila and T. Laihonen, Locating-dominating codes in cycles, Aus- tralas. J. Combin. 49 (2011) 177-194. Zbl1228.05227
  9. [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. [10] D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, Congr. Numer. 71 (1990) 153-172. Zbl0691.05043
  11. [11] F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195. Zbl0349.05118
  12. [12] T.W. Haynes, C. Sterling and P.J. Slater, Liar’s domination in ladders, Congr. Numer. 212 (2012) 45-56. Zbl1278.05180
  13. [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] Zbl1298.05236
  14. [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] Zbl1284.05197
  15. [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. Zbl1170.05306
  16. [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. [17] I. Honkala, An optimal strongly identifying code in the infinite triangular grid, Elec- tron. J. Combin. 17 (2010) R91. 
  18. [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] Zbl1082.05069
  19. [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] Zbl1122.68085
  20. [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] Zbl1005.94029
  21. [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] Zbl1105.94342
  22. [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. [23] A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs. http://www.infres.enst.fr/lobstein/debutBIBidetlocdom.pdf 
  24. [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] Zbl1100.94032
  25. [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] Zbl1284.05308
  26. [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] Zbl1297.90170
  27. [27] M.L. Roden and P.J. Slater, Liars’ domination and the domination continuum, Congr. Numer. 190 (2008) 77-85. Zbl1181.05073
  28. [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] Zbl1211.05123
  29. [29] M. Roden-Bowie and P.J. Slater, Set-sized (1, 3)-domination for trees, Congr. Nu- mer. 196 (2009) 203-213. Zbl1211.05124
  30. [30] S.J. Seo and P.J. Slater, Open neighborhood locating-dominating sets, Australas. J. Combin. 46 (2010) 109-120.[WoS] Zbl1196.05067
  31. [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] Zbl1209.05053
  32. [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. [33] S.J. Seo and P.J. Slater, Open neighborhood locating-domination for grid-like graphs, Bull. Inst. Combin. Appl. 65 (2012) 89-100. Zbl1278.05177
  34. [34] S.J. Seo and P.J. Slater,Graphical parameters for classes of tumbling block graphs, Congr. Numer. 213 (2012) 155-168. Zbl1278.05178
  35. [35] S.J. Seo and P.J. Slater, Open locating-dominating interpolation for trees, Congr. Numer. 215 (2013) 145-152.[WoS] Zbl1293.05273
  36. [36] S.J. Seo and P.J. Slater, Old trees with maximum degree three, Util. Math. 94 (2014) 361-380. Zbl1300.05234
  37. [37] J.L. Sewell, Ph.D. Dissertation, in preparation. 
  38. [38] J.L. Sewell and P.J. Slater, Fault tolerant identifying codes and locating-dominating sets, in preparation. 
  39. [39] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549-559. 
  40. [40] P.J. Slater, Domination and location in graphs, National University of Singapore, Research Report 93 (1983). 
  41. [41] P.J. Slater, Dominating and location in acyclic graphs, Networks 17 (1987) 55-64. doi:10.1002/net.3230170105[Crossref] 
  42. [42] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988) 445-455. Zbl0656.05057
  43. [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. Zbl0846.05047
  44. [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. [45] P.J. Slater, Liar’s domination, Networks 54 (2009) 70-74. doi:10.1002/net.20295[Crossref] Zbl1204.90061
  46. [46] P.J. Slater, A framework for faults in detectors within network monitoring systems, WSEAS Trans. Math. 12 (2013) 911-916. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.