×

Construction of codes identifying sets of vertices. (English) Zbl 1060.05091

Summary: The problem of constructing graphs having a \((1,\leq \ell)\)-identifying code of small cardinality is addressed. It is known that the cardinality of such a code is bounded by \(\Omega(\frac{\ell^2}{\log\ell}\log n)\). Here we construct graphs on \(n\) vertices having a \((1,\leq\! \ell)\)-identifying code of cardinality \(O(\ell^4 \log n)\) for all \(\ell\! \geq 2\). We derive our construction from a connection between identifying codes and superimposed codes, which we describe in this paper.

MSC:

05C99 Graph theory
94B60 Other types of codes
94C12 Fault detection; testing in circuits and networks