ON A NEW CLASS OF CODES FOR IDENTIFYING VERTICES IN GRAPHS

We investigate a new class of codes for the optimal covering of vertic es in an undirected graph G such that any vertex in G can be uniquely identified by examining the vertices that cover it, We define a ball o f radius t centered on a vertex upsilon to be the set of vertices in G that are at distance at most t from upsilon. The vertex upsilon is th en said to cover itself and every other vertex in the ball with center upsilon. Our formal problem statement is as follows: Given an undirec ted graph G and an integer t greater than or equal to 1, find a (minim al) set C of vertices such that every vertex in G belongs to a unique set of balls of radius t centered at the vertices in C. The set of ver tices thus obtained constitutes a code for vertex identification, We f irst develop topology-independent bounds on the size of C. We then dev elop methods for constructing C for several specific topologies such a s binary cubes, nonbinary cubes, and trees, We also describe the ident ification of sets of vertices using covering codes that uniquely ident ify single vertices. We develop methods for constructing optimal topol ogies that yield identifying codes with a minimum number of codewords, Finally, we describe an application of the theory developed in this p aper to fault diagnosis of multiprocessor systems.