February  2012, 6(1): 27-38. doi: 10.3934/amc.2012.6.27

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

1. 

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

Received  August 2010 Revised  November 2011 Published  January 2012

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)\}.$
Citation: Mikko Pelto. On $(r,\leq 2)$-locating-dominating codes in the infinite king grid. Advances in Mathematics of Communications, 2012, 6 (1) : 27-38. doi: 10.3934/amc.2012.6.27
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. doi: 10.1016/S0012-365X(03)00306-6. Google Scholar

[2]

I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs,, Electronic J. Combin., 9 (2002). Google Scholar

[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. doi: 10.1109/12.908992. Google Scholar

[4]

I. Honkala and T. Laihonen, Codes for identification in the king lattice,, Graphs Combin., 19 (2003), 505. doi: 10.1007/s00373-003-0531-2. Google Scholar

[5]

I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids,, SIAM J. Comput., 33 (2004), 304. doi: 10.1137/S0097539703433110. Google Scholar

[6]

I. Honkala and T. Laihonen, On locating-dominating sets in infinite grids,, European J. Combin., 27 (2006), 218. doi: 10.1016/j.ejc.2004.09.002. Google Scholar

[7]

I. Honkala and T. Laihonen, On a new class of identifying codes in graphs,, Inform. Proc. Letters, 102 (2007), 92. doi: 10.1016/j.ipl.2006.11.007. Google Scholar

[8]

I. Honkala, T. Laihonen and S. Ranto, On locating-dominating codes in binary Hamming spaces,, Discrete Math. Theor. Comput. Sci., 6 (2004), 265. Google Scholar

[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. doi: 10.1109/18.661507. Google Scholar

[10]

M. Pelto, New bounds for $(r,\leq 2)$-identifying codes in the infinite king grid,, Crypt. Commun., 2 (2010), 41. doi: 10.1007/s12095-009-0015-1. Google Scholar

[11]

M. Pelto, On locating-dominating codes for locating large numbers of vertices in the infinite king grid,, Australas. J. Combin., 50 (2011), 127. Google Scholar

[12]

M. Pelto, On locating-dominating codes in the infinite king grid,, Ars Combin., (). Google Scholar

[13]

M. Pelto, Optimal $(r,\leq 3)$-locating-dominating codes in the infinite king grid,, submitted., (). Google Scholar

[14]

S. Ranto, "Identifying and Locating-Dominating Codes in Binary Hamming Spaces,'', Ph.D thesis, (2007). Google Scholar

[15]

P. J. Slater, Domination and location in acyclic graphs,, Networks, 17 (1987), 55. doi: 10.1002/net.3230170105. Google Scholar

[16]

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

[17]

, URL, \url{http://www.infres.enst.fr/~lobstein/bibLOCDOMetID.html}, (). Google Scholar

show all references

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. doi: 10.1016/S0012-365X(03)00306-6. Google Scholar

[2]

I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs,, Electronic J. Combin., 9 (2002). Google Scholar

[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. doi: 10.1109/12.908992. Google Scholar

[4]

I. Honkala and T. Laihonen, Codes for identification in the king lattice,, Graphs Combin., 19 (2003), 505. doi: 10.1007/s00373-003-0531-2. Google Scholar

[5]

I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids,, SIAM J. Comput., 33 (2004), 304. doi: 10.1137/S0097539703433110. Google Scholar

[6]

I. Honkala and T. Laihonen, On locating-dominating sets in infinite grids,, European J. Combin., 27 (2006), 218. doi: 10.1016/j.ejc.2004.09.002. Google Scholar

[7]

I. Honkala and T. Laihonen, On a new class of identifying codes in graphs,, Inform. Proc. Letters, 102 (2007), 92. doi: 10.1016/j.ipl.2006.11.007. Google Scholar

[8]

I. Honkala, T. Laihonen and S. Ranto, On locating-dominating codes in binary Hamming spaces,, Discrete Math. Theor. Comput. Sci., 6 (2004), 265. Google Scholar

[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. doi: 10.1109/18.661507. Google Scholar

[10]

M. Pelto, New bounds for $(r,\leq 2)$-identifying codes in the infinite king grid,, Crypt. Commun., 2 (2010), 41. doi: 10.1007/s12095-009-0015-1. Google Scholar

[11]

M. Pelto, On locating-dominating codes for locating large numbers of vertices in the infinite king grid,, Australas. J. Combin., 50 (2011), 127. Google Scholar

[12]

M. Pelto, On locating-dominating codes in the infinite king grid,, Ars Combin., (). Google Scholar

[13]

M. Pelto, Optimal $(r,\leq 3)$-locating-dominating codes in the infinite king grid,, submitted., (). Google Scholar

[14]

S. Ranto, "Identifying and Locating-Dominating Codes in Binary Hamming Spaces,'', Ph.D thesis, (2007). Google Scholar

[15]

P. J. Slater, Domination and location in acyclic graphs,, Networks, 17 (1987), 55. doi: 10.1002/net.3230170105. Google Scholar

[16]

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

[17]

, URL, \url{http://www.infres.enst.fr/~lobstein/bibLOCDOMetID.html}, (). Google Scholar

[1]

Florent Foucaud, Tero Laihonen, Aline Parreau. An improved lower bound for $(1,\leq 2)$-identifying codes in the king grid. Advances in Mathematics of Communications, 2014, 8 (1) : 35-52. doi: 10.3934/amc.2014.8.35

[2]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[3]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[4]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[5]

Xin Xu, Jessi Cisewski-Kehe. EmT: Locating empty territories of homology group generators in a dataset. Foundations of Data Science, 2019, 1 (2) : 227-247. doi: 10.3934/fods.2019010

[6]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[7]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17

[8]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[9]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[10]

Jinchao Xu. The single-grid multilevel method and its applications. Inverse Problems & Imaging, 2013, 7 (3) : 987-1005. doi: 10.3934/ipi.2013.7.987

[11]

Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093

[12]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[13]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[14]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261

[15]

Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems & Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036

[16]

Mario Jorge Dias Carneiro, Rafael O. Ruggiero. On the graph theorem for Lagrangian minimizing tori. Discrete & Continuous Dynamical Systems - A, 2018, 38 (12) : 6029-6045. doi: 10.3934/dcds.2018260

[17]

Frédéric Sur, Michel Grédiac. Towards deconvolution to enhance the grid method for in-plane strain measurement. Inverse Problems & Imaging, 2014, 8 (1) : 259-291. doi: 10.3934/ipi.2014.8.259

[18]

Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453

[19]

Chuong Van Nguyen, Phuong Huu Hoang, Hyo-Sung Ahn. Distributed optimization algorithms for game of power generation in smart grid. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 327-348. doi: 10.3934/naco.2019022

[20]

Radu Balan, Peter G. Casazza, Christopher Heil and Zeph Landau. Density, overcompleteness, and localization of frames. Electronic Research Announcements, 2006, 12: 71-86.

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]