Geodesic
Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 853-872

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: graph, digraph, identifying code 
@article{DMGT_2021_41_4_a0,
     author = {Balbuena, Camino and Dalf\'o, Cristina and Mart{\'\i}nez-Barona, Berenice},
     title = {Sufficient {Conditions} for a {Digraph} to {Admit} {A} (1, \ensuremath{\leq} {\ensuremath{\ell})-Identifying} {Code}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {853--872},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a0/}
}
TY  - JOUR
AU  - Balbuena, Camino
AU  - Dalfó, Cristina
AU  - Martínez-Barona, Berenice
TI  - Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 853
EP  - 872
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a0/
LA  - en
ID  - DMGT_2021_41_4_a0
ER  - 
%0 Journal Article
%A Balbuena, Camino
%A Dalfó, Cristina
%A Martínez-Barona, Berenice
%T Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 853-872
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a0/
%G en
%F DMGT_2021_41_4_a0
Balbuena, Camino; Dalfó, Cristina; Martínez-Barona, Berenice. Sufficient Conditions for a Digraph to Admit A (1, ≤ ℓ)-Identifying Code. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 853-872. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a0/