dc.contributor.author	Balbuena Martínez, Camino
dc.contributor.author	Dalfó, Cristina
dc.contributor.author	Martínez Barona, Berenice
dc.date.accessioned	2020-07-02T09:05:56Z
dc.date.available	2022-05-22T22:06:54Z
dc.date.issued	2020-05-21
dc.identifier.issn	0096-3003
dc.identifier.uri	http://hdl.handle.net/10459.1/69197
dc.description.abstract	Given an integer ≥1, a (1, ≤ )-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most have distinct closed in-neighborhoods within C . In this paper, we prove that every line digraph of min- imum in-degree one does not admit a (1, ≤ )-identifying code for ≥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, ≤2)-identifying code. The identifying number of a digraph D , −→ γID (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 −→ γID (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 −→ γID (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.
dc.description.sponsorship	This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087 . The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agree- ment No 734922.
dc.format.mimetype	application/pdf
dc.language.iso	eng
dc.publisher	Elsevier
dc.relation	info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PGC2018-095471-B-I00/ES/ESTUDIO MATEMATICO DE LOS FALLOS EN CASCADA EN SISTEMAS COMPLEJOS MEDIANTE INVARIANTES Y CENTRALIDADES EN GRAFOS. APLICACIONES A REDES REALES/
dc.relation	info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016/MTM2017-83271-R/ES/CRIPTOGRAFIA Y CODIGOS PARA APLICACIONES SEGURAS Y FIABLES/
dc.relation.isformatof	Versió postprint del document publicat a: https://doi.org/10.1016/j.amc.2020.125357
dc.relation.ispartof	Applied Mathematics and Computation, 2020, vol. 383, p. 125357
dc.rights	cc-by-nc-nd, (c) Elsevier, 2020
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/es
dc.subject	Line digraph
dc.subject	Identifying code
dc.subject	Dominating set
dc.subject	Separating set
dc.subject	1-Factor
dc.title	Identifying codes in line digraphs
dc.type	info:eu-repo/semantics/article
dc.date.updated	2020-07-02T09:05:56Z
dc.identifier.idgrec	029991
dc.type.version	info:eu-repo/semantics/acceptedVersion
dc.rights.accessRights	info:eu-repo/semantics/openAccess
dc.identifier.doi	https://doi.org/10.1016/j.amc.2020.125357
dc.relation.projectID	info:eu-repo/grantAgreement/EC/H2020/734922/EU/CONNECT

Identifying codes in line digraphs

Files in this item

This item appears in the following Collection(s)