Construction of Codes Identifying Sets of Vertices

Source abstract

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