PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 4 | 797-818
Tytuł artykułu

Fault Tolerant Detectors for Distinguishing Sets in Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
35
Numer
4
Strony
797-818
Opis fizyczny
Daty
wydano
2015-11-01
otrzymano
2014-10-27
poprawiono
2015-04-07
zaakceptowano
2015-04-07
online
2015-11-10
Twórcy
autor
  • Computer Science Department Middle Tennessee State University Murfreesboro, TN 37132, USA, Suk.Seo@mtsu.edu
  • Mathematical Sciences Department and Computer Science Department University of Alabama in Huntsville Huntsville, AL 35899 USA, slater@uah.edu
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1838
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.