Show simple item record

dc.contributor.authorBalbuena Martínez, Camino
dc.contributor.authorDalfó, Cristina
dc.contributor.authorMartínez Barona, Berenice
dc.date.accessioned2020-07-02T09:05:56Z
dc.date.available2022-05-22T22:06:54Z
dc.date.issued2020-05-21
dc.identifier.issn0096-3003
dc.identifier.urihttp://hdl.handle.net/10459.1/69197
dc.description.abstractGiven 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.sponsorshipThis 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.mimetypeapplication/pdf
dc.language.isoeng
dc.publisherElsevier
dc.relationinfo: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.relationinfo: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.isformatofVersió postprint del document publicat a: https://doi.org/10.1016/j.amc.2020.125357
dc.relation.ispartofApplied Mathematics and Computation, 2020, vol. 383, p. 125357
dc.rightscc-by-nc-nd, (c) Elsevier, 2020
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es
dc.subjectLine digraph
dc.subjectIdentifying code
dc.subjectDominating set
dc.subjectSeparating set
dc.subject1-Factor
dc.titleIdentifying codes in line digraphs
dc.typeinfo:eu-repo/semantics/article
dc.date.updated2020-07-02T09:05:56Z
dc.identifier.idgrec029991
dc.type.versioninfo:eu-repo/semantics/acceptedVersion
dc.rights.accessRightsinfo:eu-repo/semantics/openAccess
dc.identifier.doihttps://doi.org/10.1016/j.amc.2020.125357
dc.relation.projectIDinfo:eu-repo/grantAgreement/EC/H2020/734922/EU/CONNECT


Files in this item

Thumbnail
Thumbnail
Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

cc-by-nc-nd, (c) Elsevier, 2020
Except where otherwise noted, this item's license is described as cc-by-nc-nd, (c) Elsevier, 2020