Sufficient conditions for a digraph to admit a $(1,\le \ell )$-identifying code

Abstract

A $(1,\le \ell )$-identifying code in a digraph $D$ is a subset $C$ of vertices of $D$ such that all distinct subsets of vertices of cardinality at most $\ell$ have different closed in-neighborhoods within $C$. In this paper, we give some sufficient conditions for a digraph of minimum in-degree ${\delta }^{-}\ge 1$ to admit a $(1,\le \ell )$-identifying code for $\ell ={\delta }^{-},{\delta }^{-}+1$. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree $\delta \ge 2$ and girth at least 7 admits a $(1,\le \delta )$-identifying code. Moreover, we prove that every $1$-in-regular digraph has a $(1,\le 2)$-identifying code if and only if the girth of the digraph is at least 5. We also characterize all the 2-in-regular digraphs admitting a $(1,\le \ell )$-identifying code for $\ell =2,3$.