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.