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/

[1] G. Araujo-Pardo, C. Balbuena, L. Montejano and J.C. Valenzuela, Partial linear spaces and identifying codes, European J. Combin. 32 (2011) 344–351. https://doi.org/10.1016/j.ejc.2010.10.014

[2] C. Balbuena, C. Dalfó and B. Martínez-Barona, Characterizing identifying codes from the spectrum of a graph or digraph, Linear Algebra Appl. 570 (2019) 138–147. https://doi.org/10.1016/j.laa.2019.02.010

[3] C. Balbuena, F. Foucaud and A. Hansberg, Locating-dominating sets and identifying codes in graphs of girth at least 5, Electron. J. Combin. 22 (2) (2015) #P2.15. https://doi.org/10.37236/4562

[4] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2007). https://doi.org/10.1007/978-1-84800-998-1

[5] N. Bertrand, I. Charon, O. Hudry and A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European J. Combin. 25 (2004) 969–987. https://doi.org/10.1016/j.ejc.2003.12.013

[6] I. Charon, G. Cohen, O. Hudry and A. Lobstein, New identifying codes in the binary Hamming space, European J. Combin. 31 (2010) 491–501. https://doi.org/10.1016/j.ejc.2009.03.032

[7] I. Charon, O. Hudry and A. Lobstein, Identifying and locating-dominating codes: NP-completeness results for directed graphs, IEEE Trans. Inform. Theory 48 (2002) 2192–2200. https://doi.org/10.1109/TIT.2002.800490

[8] I. Charon, S. Gravier, O. Hudry, A. Lobstein, M. Mollard and J. Moncel, A linear algorithm for minimum 1 -identifying codes in oriented trees, Discrete Appl. Math. 154 (2006) 1246–1253. https://doi.org/10.1016/j.dam.2005.11.007

[9] G. Exoo, V. Junnila, T. Laihonen and S. Ranto, Upper bounds for binary identifying codes, Adv. Appl. Math. 42 (2009) 277–289. https://doi.org/10.1016/j.aam.2008.06.004

[10] G. Exoo, V. Junnila, T. Laihonen and S. Ranto, Improved bounds on identifying codes in binary Hamming spaces, European J. Combin. 31 (2010) 813–827. https://doi.org/10.1016/j.ejc.2009.09.002

[11] F. Foucaud, R. Naserasr and A. Parreau, Characterizing extremal digraphs for identifying codes and extremal cases of Bondy’s Theorem on induced subsets, Graphs Combin. 29 (2013) 463–473. https://doi.org/10.1007/s00373-012-1136-4

[12] A. Frieze, R. Martin, J. Moncel, M. Ruszinkó and C. Smyth, Codes identifying sets of vertices in random networks, Discrete Math. 307 (2007) 1094–1107. https://doi.org/10.1016/j.disc.2006.07.041

[13] S. Gravier and J. Moncel, Construction of codes identifying sets of vertices, Electron. J. Combin. 12 (2005) #R13. https://doi.org/10.37236/1910

[14] S. Gravier, A. Parreau, S. Rottey, L. Storme and E. Vandomme, Identifying codes in vertex-transitive graphs and strongly regular graphs, Electron. J. Combin. 22 (2015) #P4.6. https://doi.org/10.37236/5256

[15] I. Honkala and T. Laihonen, On identifying codes in the king grid that are robust against edge deletions, Electron. J. Combin. 15 (2008) #R3. https://doi.org/10.37236/727

[16] M. Karpovsky, K. Chakrabarty and L. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (1998) 599–611. https://doi.org/10.1109/18.661507

[17] T. Laihonen, On cages admitting identifying codes, European J. Combin. 29 (2008) 737–741. https://doi.org/10.1016/j.ejc.2007.02.016

[18] T. Laihonen and S. Ranto, Codes identifying sets of vertices, Lecture Notes in Comput. Sci. 2227 (2001) 82–91. https://doi.org/10.1007/3-540-45624-4_9

[19] A. Lobstein. https://www.lri.fr/~lobstein/bibLOCDOMetID.html