Identifying codes of cycles (Q2488842)

We deal with identifying codes in cycles and show that for all \(r\geq 1\), any \(r\)-identifying code of the cycle \({\mathcal C}_n\) has cardinality at least \(\text{gcd}(2r+1,n)\left\lceil\frac{n}{2\text{gcd}(2r+1,n)}\right\rceil\).. This lower bound is enough to solve the case \(n\) even (which was already solved in [\textit{N. Bertrand, I. Charon, O. Hudry}, and \textit{A. Lobstein} [Eur. J. Comb. 25, No.~7, 969--987 (2004; Zbl 1053.05095)], but the case \(n\) odd seems to be more complicated. An upper bound is given for the case \(n\) odd, and some special cases are solved. Furthermore, we give some conditions on \(n\) and \(r\) to attain the lower bound.