Optimal Identifying Codes in Cycles and Paths

Abstract

The concept of identifying codes in a graph was introduced by Karpovsky et al. (in IEEE Trans Inf Theory 44(2):599-611, 1998). These codes have been studied in several types of graphs such as hypercubes, trees, the square grid, the triangular grid, cycles and paths. In this paper, we determine the optimal cardinalities of identifying codes in cycles and paths in the remaining open cases.