| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421498 | Discrete Applied Mathematics | 2006 | 8 Pages |
Abstract
Identifying codes were defined to model fault diagnosis in multiprocessor systems. They are also used for the design of indoor detection systems based on wireless sensor networks. When designing such systems, one is usually interested in finding a network structure which minimizes the cardinality of such a code. Given a graph G on n vertices, it is easy to see that the minimum cardinality of an identifying code of G is at least ⌈log2(n+1)⌉⌈log2(n+1)⌉. In this paper, we provide a construction of all the optimal graphs for the identification of vertices, that is to say graphs on n vertices having an identifying code of cardinality ⌈log2(n+1)⌉⌈log2(n+1)⌉. We also compute various parameters of these graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Julien Moncel,