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 |