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

• Published in: arXiv.org 2019-02
• Main Authors: Balbuena, C, Dalfó, C, Martínez-Barona, B
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory
• ISSN: 2331-8422

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\).