Show simple item record

dc.contributor.authorBalbuena Martínez, Camino
dc.contributor.authorDalfó, Cristina
dc.contributor.authorMartínez Barona, Berenice
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.publisherUniversity of Zielona Góra
dc.relation.isformatofReproducció del document publicat a
dc.relation.ispartofDiscussiones Mathematicae Graph Theory, 2019
dc.rightscc-by-nc-nd (c) Balbuena et al., 2019
dc.subject.otherIdentifying code
dc.titleSufficient conditions for a digraph to admit a (1,≤ℓ)-identifying code

Files in this item


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