<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue3" %>
An Optimal Edge-Robust Identifying Code in the Triangular Lattice
Iiro Honkala
Department of Mathematics, University of Turku, 20014 Turku, Finland
honkala@utu.fi
Annals of Combinatorics 8 (3) p.303-323 September, 2004
AMS Subject Classification:05C70, 68R10, 94B65
Abstract:
A subset C of vertices in an undirected graph G=(V, E) is called a 1-identifying code if the sets I(v) ={uC : d(u, v)1}, vV, are non-empty and no two of them are the same set. A 1-identifying code C is called 1-edge-robust 1-identifying if it is 1-identifying in every graph G1 obtained from G by deleting or adding one edge. It is shown that the optimal density of a 1-edge-robust 1-identifying code in the infinite triangular lattice is 3/7.
Keywords: identifying code, triangular lattice, density, graph

References:

1. I. Charon, I. Honkala, O. Hudry, and A. Lobstein, General bounds for identifying codes in some infinite regular graphs, Elect. J. Combin. 8 (2001) #R39.

2. I. Charon, I. Honkala, O. Hudry, and A. Lobstein, The minimum density of an identifying code in the king lattice, Discrete Math. 276 (2004) 95--109.

3. I. Charon, O. Hudry, and A. Lobstein, Identifying codes with small radius in some infinite regular graphs, Elect. J. Combin. 9 (2002) #R11.

4. T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.

5. I. Honkala, M.G. Karpovsky, and L.B. Levitin, On robust identifying codes, preprint.

6. I. Honkala and T. Laihonen, On the identification of sets of points in the square lattice, Discrete Comput. Geom. 29 (2003) 139--152.

7. I. Honkala and T. Laihonen, Codes for identification in the king lattice, Graphs Combin. 19 (2003) 505--516.

8. I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput. 33 (2004) 304--312.

9. I. Honkala and T. Laihonen, On identifying codes in the hexagonal mesh, Inform. Process. Lett. 89 (2004) 9--14.

10. I. Honkala and A. Lobstein, On the density of identifying codes in the square lattice, J. Combin. Theory, Ser. B 85 (2002) 297--306.

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

12. D.F. Rall and P.J. Slater, On locationí¬domination numbers for certain classes of graphs, Congr. Numer. 45 (1984) 97--106.

13. S. Ray, R. Ungrangsi, F. De Pellegrini, A. Trachtenberg, and D. Starobinski, Robust location detection in emergency sensor networks, In: Proceedings of INFOCOM 2003, San Francisco, March 2003.

14. P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988) 445--455.

15. P.J. Slater, Locating dominating sets and locating-dominating sets, In: Graph Theory, Combinatorics and Applications: Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Vol. 2, Wiley, 1995, pp. 1073--1079.

16. P.J. Slater, Fault-tolerating locating-dominating sets, Discrete Math. 249 (2002) 179--189.