Identifying codes in line digraphs
Given an integer \ell\ge 1$ a (1,\le \ell) identifying code in a digraph is a dominating subset $C$ of vertices such that all distinct subsets of vertices of cardinality at most \ell$ have distinct closed in neighbourhood within $C$ In this paper, we prove that every $k$ iterated line digraph of minimum in degree at least 2 and $k\geq2$ or minimum in degree at least 3 and $k\geq1$ admits a (1,\le \ell) identifying code with \ell\leq2$ and in any case it does not admit a (1,\le \ell) identifying code for \ell\geq3$ Moreover, we find that the identifying number of a line digraph is lower bounded by the size of the original digraph minus its order. Furthermore, this lower bound is attained for oriented graphs of minimum in degree at least 2.
Appl. Math. Comput.