×

The number of completely different optimal identifying codes in the infinite square grid. (English) Zbl 1403.94129

Summary: Let \(G\) be a graph with vertex set \(V\) and edge set \(E\). We call any subset \(C\subseteq V\) an identifying code if the sets \[ I(v)=\{c\in C\mid \{c,v\}\in E\,\text{or}\, c=v\} \] are distinct and non-empty for all vertices \(v\in V\). We study identifying codes in the infinite square grid. The vertex set of this graph is \(\mathbb{Z}^2\) and two vertices are connected by an edge if the Euclidean distance between these vertices is one. Y. Ben-Haim and S. Litsyn [SIAM J. Discrete Math. 19, No. 1, 69–82 (2005; Zbl 1085.94026)] have proved that the minimum density of identifying code in the infinite square grid is \(\frac{7}{20}\). Such codes are called optimal. We study the number of completely different optimal identifying codes in the infinite square grid. Two codes are called completely different if there exists an integer \(n\) such that no \(n\times n\)-square of one code is equivalent with any \(n\times n\)-square of the other code. In particular, we show that there are exactly two completely different optimal periodic codes and no optimal identifying code is completely different with both of these two periodic codes.

MSC:

94B99 Theory of error-correcting codes and error-detecting codes
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C62 Graph representations (geometric and intersection representations, etc.)
52C05 Lattices and convex bodies in \(2\) dimensions (aspects of discrete geometry)

Citations:

Zbl 1085.94026
Full Text: DOI

References:

[1] Ben-Haim, Y.; Litsyn, S., Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math., 19, 69-82 (2005) · Zbl 1085.94026
[2] Cohen, G.; Gravier, S.; Honkala, I.; Lobstein, A.; Mollard, M.; Payan, Ch.; Zémor, G., Improved identifying codes for the grid, Electron. J. Combin., 6, 1 (1999), Comments to R19
[3] Karpovsky, M. G.; Chakrabarty, K.; Levitin, L. B., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, IT-44, 599-611 (1998) · Zbl 1105.94342
[5] Slater, P. J., Domination and location in acyclic graphs, Networks, 17, 55-64 (1987) · Zbl 0643.90089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.