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