Identifying codes in digraphs

A (1,\le \ell)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most \ell have distinct closed in-neighbourhoods within C.

In this talk, we give an upper bound on \ell and 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. We give also a new method to obtain an upper bound on \ell for digraphs and graphs using spectral graph theory. As particular cases, we give a characterization of the j-in-regular digraphs admitting a (1,\le \ell)-identifying code for j \in \{1,2\} and \ell\in\{1,2,3\}. We also prove that every k-iterated line digraph of minimum in-degree at least 2 admits a (1,\le \ell)-identifying code with \ell \le 2, and it does not admit a (1,\le \ell)-identifying code for \ell\ge 3. Moreover, we give some bounds of the identifying number of a line digraph, that is, the minimum size of a (1,\le 1)-identifying code.