Sufficient conditions for a digraph to admit a (1,≤ l)-identifying code
Camino Balbuena, C. Dalfó, B. Martínez-Barona · Discussiones Mathematicae Graph Theory · 2019
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}.