On graphs on n vertices having an identifying code of cardinality [log2(n+1)]

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 [log(2)(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 [log(2)(n + 1)]. We also compute various parameters of these graphs. (c) 2006 Elsevier B.V. All rights reserved.