Optimal identifying codes in the infinite 3-dimensional king grid

: Pelto M.

: 2014

: European Journal of Combinatorics

: 36

: 641

: 659

: 19

: 0195-6698

DOI: https://doi.org/10.1016/j.ejc.2013.10.002

: http://api.elsevier.com/content/abstract/scopus_id:84886824637

A subset C ⊆ V is an r-identifying code in a graph G = (. V, E) if the sets Ir(v)={c∈C{divides}d(c,v)≤r} are distinct and non-empty for all vertices v⊆V. Here, d(c,v) denotes the number of edges on any shortest path from c to v. We consider the infinite n-dimensional king grid, i.e., the graph with vertex set V=Zn and the edge set E={{x=(x1,...,xn),y=(y1,...,yn)}{divides}|xi-yi|≤1for i=1,...,n,x≠y}, and give some lower bounds on the density of an r-identifying code. In particular, we prove that for n = 3 and for all r ≥ 15, the optimal density of an r-identifying code is 18r2. The problem finding a minimum identifying code in the 3-dimensional king grid is equivalent with a minimum packing problem of cubes in the 3-dimensional lattice so that every point is covered by a distinct and non-empty subset of cubes. © 2013 Elsevier Ltd.

Mathematics