Codes identifying sets of vertices in random networks

AbstractIn this paper we deal with codes identifying sets of vertices in random networks; that is, (1,⩽ℓ)-identifying codes. These codes enable us to detect sets of faulty processors in a multiprocessor system, assuming that the maximum number of faulty processors is bounded by a fixed constant ℓ. The (1,⩽1)-identifying codes are of special interest. For random graphs we use the model G(n,p), in which each one of the (n2) possible edges exists with probability p. We give upper and lower bounds on the minimum cardinality of a (1,⩽ℓ)-identifying code in a random graph, as well as threshold functions for the property of admitting such a code. We derive existence results from probabilistic constructions. A connection between identifying codes and superimposed codes is also established