On cages admitting identifying codes (Q2426452)

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.