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 ellin{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 ellge 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.