Sufficient conditions for a digraph to admit a (1,≤ℓ)-identifying code

Abstract

A (1, ≤ `)-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 ` have distinct closed in-neighbourhoods within C. In this paper, we give some sufficient conditions for a digraph of minimum in-degree δ − ≥ 1 to admit a (1, ≤ `)- identifying code for ` ∈ {δ −, δ− + 1}. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree δ ≥ 2 and girth at least 7 admits a (1, ≤ δ)-identifying code. Moreover, we prove that every 1-in-regular digraph has a (1, ≤ 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, ≤ `)-identifying code for ` ∈ {2, 3}.

This research has been partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Generalitat de Catalunya. The last two authors have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.