Adaptive identification in graphs (Q958720)

Let \(G\) be a given (undirected and connected) graph and let \(r\) denote a positive integer. A code \(C\) is a subset of vertices of \(G\) and vertices in \(C\) are called the codewords. \(C\) is called an \(r\)-covering code if for any vertex \(v\) of \(G\), the ball of radius \(r\) centered at \(v\) has at least one codeword. and \(C\) is called an \(r\)-packing if the \(r\)-balls centered at the codewords are disjoint. \(C\) is called an \(r\)-identifying code if \(\forall v \neq v'\) in \(V = V(G)\), the sets \(C \cap B_r(v)\) and \(C \cap B_r(v')\) are distinct (here \(B_r(x)\) means the ball of radius \(r\) centered at \(x\)). This paper introduces an adaptive version of identifying codes. These codes are motivated by various engineering applications. Bounds on adaptive identifying codes are given for regular graphs and torii in the square grid. The new codes.are compared to the classical non-adaptive case.