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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references