Show simple item record

dc.contributor.authorBalbuena Martínez, Camino
dc.contributor.authorDalfó, Cristina
dc.contributor.authorMartínez Barona, Berenice
dc.date.accessioned2019-05-29T08:40:21Z
dc.date.available2019-05-29T08:40:21Z
dc.date.issued2019
dc.identifier.issn1234-3099
dc.identifier.urihttp://hdl.handle.net/10459.1/66389
dc.description.abstractA (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}.
dc.description.sponsorshipThis research has been partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Generalitat de Catalunya. The last two authors have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.publisherUniversity of Zielona Góra
dc.relation.isformatofReproducció del document publicat a https://doi.org/10.7151/dmgt.2218
dc.relation.ispartofDiscussiones Mathematicae Graph Theory, 2019
dc.rightscc-by-nc-nd (c) Balbuena et al., 2019
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/
dc.subject.otherGraph
dc.subject.otherDigraph
dc.subject.otherIdentifying code
dc.titleSufficient conditions for a digraph to admit a (1,≤ℓ)-identifying code
dc.typeinfo:eu-repo/semantics/article
dc.date.updated2019-05-29T08:40:21Z
dc.identifier.idgrec028537
dc.rights.accessRightsinfo:eu-repo/semantics/openAccess
dc.identifier.doihttps://doi.org/10.7151/dmgt.2218
dc.relation.projectIDinfo:eu-repo/grantAgreement/EC/H2020/734922/EU/CONNECT


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

cc-by-nc-nd (c) Balbuena et al., 2019
Except where otherwise noted, this item's license is described as cc-by-nc-nd (c) Balbuena et al., 2019