Identifying codes in line digraphs

Abstract

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\ge 2$, or minimum in-degree at least 3 and $k\ge 1$, admits a $(1,\le \ell )$-identifying code with $\ell \le 2$, and in any case it does not admit a $(1,\le \ell )$-identifying code for $\ell \ge 3$. 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.