On Locating-Dominating Codes in the Infinite King Grid

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\). A subset \(C \subseteq V\) is called an \(r\)-locating-dominating code if the sets \(I_r(v) = B_r(v) \cap C\) are distinct and non-empty for all \(v \in V \setminus C\). A code \(C\) is an \(r\)-identifying code if the sets \(I_r(v) = B_r(v) \cap C\) are distinct and non-empty for all vertices \(v \in V\). We study \(r\)-locating-dominating codes in the infinite king grid and, in particular, show that there is an \(r\)-locating-dominating code such that every \(r\)-identifying code has larger density. The infinite king grid is the graph with vertex set \(\mathbb{Z}^2\) and edge set \(\{(x_1, y_1), (x_2, y_2) \mid |x_1 – x_2| \leq 1, |y_1 – y_2| \leq 1, (x_1, y_1) \neq (x_2, y_2)\}\).