On cages admitting identifying codes (Q2426452)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On cages admitting identifying codes
scientific article

    Statements

    On cages admitting identifying codes (English)
    0 references
    0 references
    22 April 2008
    0 references
    The motivation for identifying codes, introduced in [IEEE Trans. Inf. Theory 44, No. 2, 599--611 (1998; Zbl 1105.94342)] by \textit{M. G. Karpovsky}, \textit{K. Chakrabarty} and \textit{L. B. Levitin}, comes from finding faulty processors in a multiprocessor system. The system is modelled as a graph; the vertices correspond to processors and edges to the communication links between them. This paper considers a problem concerning the existence of \(\ell\)-regular graphs admitting \((1,\leq\ell)\)-identifying code. The girth approach followed gives improvements on the number of vertices of graphs which admit identifying codes.
    0 references
    identifying codes
    0 references
    regular graphs
    0 references
    girth
    0 references

    Identifiers