Construction of codes identifying sets of vertices (Q1773205)

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.