×

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

Summary: A \((1, \leq \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 distinct closed in-neighbourhoods within \(C\). In this paper, we give some sufficient conditions for a digraph of minimum in-degree \(\delta^- \geq 1\) to admit a \((1, \leq \ell )\)-identifying code for \(\ell \in\{ \delta^-, \delta^- + 1\}\). As a corollary, we obtain the result by T. Laihonen [Eur. J. Comb. 29, No. 3, 737–741 (2008; Zbl 1143.05036)] that states that a graph of minimum degree \(\delta \geq 2\) and girth at least 7 admits a \((1, \leq \delta )\)-identifying code. Moreover, we prove that every 1-in-regular digraph has a \((1, \leq 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, \leq \ell )\)-identifying code for \(\ell \in \{2, 3\}\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
94B60 Other types of codes
94B25 Combinatorial codes

Citations:

Zbl 1143.05036
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[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. doi:10.1016/j.ejc.2010.10.014 · Zbl 1213.05041
[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. doi:10.1016/j.laa.2019.02.010 Sufficient Conditions for a Digraph to Admit ... 871 · Zbl 1411.05098
[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. doi:10.37236/4562 · Zbl 1311.05144
[4] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2007). doi:10.1007/978-1-84800-998-1 · Zbl 1001.05002
[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. doi:10.1016/j.ejc.2003.12.013 · Zbl 1053.05095
[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. doi:10.1016/j.ejc.2009.03.032 · Zbl 1198.94175
[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. doi:10.1109/TIT.2002.800490 · Zbl 1062.94056
[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. doi:10.1016/j.dam.2005.11.007 · Zbl 1103.68130
[9] G. Exoo, V. Junnila, T. Laihonen and S. Ranto, Upper bounds for binary identifying codes, Adv. Appl. Math. 42 (2009) 277-289. doi:10.1016/j.aam.2008.06.004 · Zbl 1182.94067
[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. doi:10.1016/j.ejc.2009.09.002 · Zbl 1196.94094
[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. doi:10.1007/s00373-012-1136-4 · Zbl 1267.05132
[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. doi:10.1016/j.disc.2006.07.041 · Zbl 1160.94021
[13] S. Gravier and J. Moncel, Construction of codes identifying sets of vertices, Electron. J. Combin. 12 (2005) #R13. doi:10.37236/1910 · Zbl 1060.05091
[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. doi:10.37236/5256 · Zbl 1323.05141
[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. doi:10.37236/727 · Zbl 1159.05041
[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. doi:10.1109/18.661507 · Zbl 1105.94342
[17] T. Laihonen, On cages admitting identifying codes, European J. Combin. 29 (2008) 737-741. doi:10.1016/j.ejc.2007.02.016 · Zbl 1143.05036
[18] T. Laihonen and S. Ranto, Codes identifying sets of vertices, Lecture Notes in Comput. Sci. 2227 (2001) 82-91. doi:10.1007/3-540-45624-4_9 · Zbl 1057.94035
[19] A. Lobstein. https://www.lri.fr/ lobstein/bibLOCDOMetID.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.