Optimal Identifying Codes in Cycles and Paths
: Junnila V, Laihonen T
Publisher: SPRINGER TOKYO
: 2012
: Graphs and Combinatorics
: GRAPHS AND COMBINATORICS
: GRAPH COMBINATOR
: 4
: 28
: 4
: 469
: 481
: 13
: 0911-0119
DOI: https://doi.org/10.1007/s00373-011-1058-6(external)
: https://research.utu.fi/converis/portal/detail/Publication/2680484(external)
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.