Article Contents

2012, Volume 6, Issue 1: 27-38. Doi: 10.3934/amc.2012.6.27

This issue Previous Article Algebraic reduction for the Golden Code Next Article Skew constacyclic codes over finite chain rings

On $(r,\leq 2)$-locating-dominating codes in the infinite king grid

Mikko Pelto^1,

1.
Turku Centre for Computer Science TUCS, Department of Mathematics, University of Turku, FI-20014 Turku

Received: August 2010

Revised: November 2011

Published: February 2012

Abstract / Introduction Related Papers Cited by

Abstract

Assume that $G=(V,E)$ is an undirected graph with vertex set $V$ and edge set $E$. The ball $B_r(v)$ denotes the vertices within graphical distance $r$ from $v$. Let $I_r(F)=\bigcup$_{$v\in F$}$(B_r(v) \cap C)$ be a set of codewords in the neighbourhoods of vertices $v\in F$. A subset $C\subseteq V$ is called an $(r,\leq l)$-locating-dominating code of type A if sets $I_r(F_1)$ and $I_r(F_2)$ are distinct for all subsets $F_1,F_2\subseteq V$ where $F_1\ne F_2$, $F_1\cap C= F_2 \cap C$ and $|F_1|,|F_2| \leq l$. A subset $C\subseteq V$ is an $(r,\leq l)$-locating-dominating code of type B if the sets $I_r(F)$ are distinct for all subsets $F\subseteq V\setminus C$ with at most $l$ vertices. We study $(r,\leq l)$-locating-dominating codes in the infinite king grid when $r\geq 1$ and $l=2$. The infinite king grid is the graph with vertex set $\mathbb Z^2$ and edge set $\{\{(x_1,y_1),(x_2,y_2)\}||x_1-x_2|\leq 1, |y_1-y_2|\leq 1, (x_1,y_1)\ne(x_2,y_2)\}.$

Keywords:

Mathematics Subject Classification: Primary: 05C69, 94B65; Secondary: 68R05, 94C12.

Citation:

Related Papers

Cited by

References

[1]	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.doi: 10.1016/S0012-365X(03)00306-6.
[2]	I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs, Electronic J. Combin., 9 (2002), R11.
[3]	G. Cohen, I. Honkala, A. Lobstein and G. Zémor, On codes identifying vertices in the two-dimensional square lattice with diagonals, IEEE Trans. Comput., 50 (2001), 174-176.doi: 10.1109/12.908992.
[4]	I. Honkala and T. Laihonen, Codes for identification in the king lattice, Graphs Combin., 19 (2003), 505-516.doi: 10.1007/s00373-003-0531-2.
[5]	I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput., 33 (2004), 304-312.doi: 10.1137/S0097539703433110.
[6]	I. Honkala and T. Laihonen, On locating-dominating sets in infinite grids, European J. Combin., 27 (2006), 218-227.doi: 10.1016/j.ejc.2004.09.002.
[7]	I. Honkala and T. Laihonen, On a new class of identifying codes in graphs, Inform. Proc. Letters, 102 (2007), 92-98.doi: 10.1016/j.ipl.2006.11.007.
[8]	I. Honkala, T. Laihonen and S. Ranto, On locating-dominating codes in binary Hamming spaces, Discrete Math. Theor. Comput. Sci., 6 (2004), 265-282,.
[9]	M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Informa. Theory, IT-44 (1998), 599-611.doi: 10.1109/18.661507.
[10]	M. Pelto, New bounds for $(r,\leq 2)$-identifying codes in the infinite king grid, Crypt. Commun., 2 (2010), 41-47.doi: 10.1007/s12095-009-0015-1.
[11]	M. Pelto, On locating-dominating codes for locating large numbers of vertices in the infinite king grid, Australas. J. Combin., 50 (2011), 127-139,.
[12]	M. Pelto, On locating-dominating codes in the infinite king grid, Ars Combin., to appear.
[13]	M. Pelto, Optimal $(r,\leq 3)$-locating-dominating codes in the infinite king grid, submitted.
[14]	S. Ranto, "Identifying and Locating-Dominating Codes in Binary Hamming Spaces,'' Ph.D thesis, University of Turku, Finland, 2007.
[15]	P. J. Slater, Domination and location in acyclic graphs, Networks, 17 (1987), 55-64.doi: 10.1002/net.3230170105.
[16]	P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22 (1988), 445-455.
[17]	URL http://www.infres.enst.fr/~lobstein/bibLOCDOMetID.html