×

Identifying codes in line digraphs. (English) Zbl 1462.05268

Summary: Given an integer \(\ell \geq 1\), a \((1, \leq \ell)\)-identifying code in a digraph is a dominating subset \(C\) of vertices such that all distinct subsets of vertices of cardinality at most \(\ell\) have distinct closed in-neighborhoods within \(C\). In this paper, we prove that every line digraph of minimum in-degree one does not admit a \((1, \leq \ell)\)-identifying code for \(\ell \geq 3\). Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a \((1, \leq 2)\)-identifying code. The identifying number of a digraph \(D\), \(\overrightarrow{\gamma}^{I D} (D)\), is the minimum size of all the identifying codes of \(D\). We establish for digraphs without digons with both vertices of in-degree one that \(\overrightarrow{\gamma}^{I D} (LD)\) is lower bounded by the number of arcs of \(D\) minus the number of vertices with out-degree at least one. Then we show that \(\overrightarrow{\gamma}^{I D} (LD)\) attains the equality for a digraph having a 1-factor with minimum in-degree two and without digons with both vertices of in-degree two. We finish by giving an algorithm to construct identifying codes in oriented digraphs with minimum in-degree at least two and minimum out-degree at least one.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20 Directed graphs (digraphs), tournaments
94B60 Other types of codes
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Aigner, M., On the linegraph of a directed graph, Math. Z., 102, 56-61 (1967) · Zbl 0158.20901
[2] In press. www.dmgt.uz.zgora.pl/publish/view_press.php?ID=4688. · Zbl 1411.05098
[3] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2007), Springer-Verlag: Springer-Verlag London
[4] Beineke, L.; Zamfirescu, C., Connection digraphs and second-order line digraphs, Discrete Math., 39, 237-254 (1982) · Zbl 0483.05031
[5] Charon, I.; Gravier, S.; Hudry, O.; Lobstein, A.; Mollard, M.; Moncel, J., A linear algorithm for minimum 1-identifying codes in oriented trees, Discrete Appl. Math., 154, 1246-1253 (2006) · Zbl 1103.68130
[6] Charon, I.; Hudry, O.; Lobstein, A., Identifying and locating-dominating codes: NP-completeness results for directed graphs, IEEE Trans. Inform. Theory, 48, 2192-2200 (2002) · Zbl 1062.94056
[7] Foucaud, F.; Gravier, S.; Naserasr, R.; Parreau, A.; Valicov, P., Identifying codes in line graphs, J. Graph Theory, 73, 425-448 (2013) · Zbl 1269.05092
[8] Foucaud, F.; Naserasr, R.; Parreau, A., Characterizing extremal digraphs for identifying codes and extremal cases of bondy’s theorem on induced subsets, Graphs Combin., 29, 463-473 (2013) · Zbl 1267.05132
[9] Fiol, M. A.; Yebra, J. L.A.; Alegre, I., Line digraph iterations and the (d, k) digraph problem, IEEE Trans. Comput., C-33, 400-403 (1984) · Zbl 0528.68048
[10] Heuchenne, C., Sur une certaine correspondance entre graphes, Bull. Soc. Roy. Sc. Liège, 33, 174-177 (1964) · Zbl 0134.43302
[11] Junnila, V.; Laihonen, T., Optimal identification of sets of edges using 2-factors, Discrete Math., 313, 1636-1647 (2013) · Zbl 1281.05116
[12] Karpovsky, M.; Chakrabarty, K.; Levitin, L., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44, 599-611 (1998) · Zbl 1105.94342
[13] M. Laifenfeld, A. Trachtenberg, R. Cohen, D. Starobinski, Joint monitoring and routing in wireless sensor networks using robust identifying codes, 2007, 2007, 197-206.
[14] Reddy, S. M.; Kuhl, J. G.; Hosseini, S. H.; Lee, H., On digraphs with minimum diameter and maximum connectivity, Proc. 20th Annual Allerton Conference, 1018-1026 (1982)
[15] (http://hdl.handle.net/105000/2226).
[16] Tvrdík, P., Necklaces and scalability of Kautz digraphs, Proc. of the Sixth IEEE Symp. on Parallel and Distributed Processing, 409-415 (1994), IEEE CS Press: IEEE CS Press Los Alamitos
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.