Identifying codes of cycles (Q2488842)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Identifying codes of cycles |
scientific article |
Statements
Identifying codes of cycles (English)
0 references
16 May 2006
0 references
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.
0 references
0 references