\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
\nopagenumbers
\noindent
%
%
{\bf Sylvain Gravier and Julien Moncel}
%
%
\medskip
\noindent
%
%
{\bf Construction of Codes Identifying Sets of Vertices}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.

\bye

.
