Identifying codes in line digraphs

View/ Open
Issue date
2020-05-21Suggested citation
Balbuena Martínez, Camino;
Dalfó, Cristina;
Martínez Barona, Berenice;
.
(2020)
.
Identifying codes in line digraphs.
Applied Mathematics and Computation, 2020, vol. 383, p. 125357.
https://doi.org/10.1016/j.amc.2020.125357.
Metadata
Show full item recordAbstract
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.
Is part of
Applied Mathematics and Computation, 2020, vol. 383, p. 125357European research projects
The following license files are associated with this item:
Related items
Showing items related by title, author, creator and subject.
-
Sufficient conditions for a digraph to admit a (1,≤ℓ)-identifying code
Balbuena Martínez, Camino; Dalfó, Cristina; Martínez Barona, Berenice (University of Zielona Góra, 2019)A (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 ... -
Characterizing identifying codes from the spectrum of a graph or digraph
Balbuena Martínez, Camino; Dalfó, Cristina; Martínez Barona, Berenice (Elsevier, 2019)A (1, ≤ ℓ)-identifying code in digraph D is a dominating subset C of vertices of D, such that all distinct subsets of vertices of D with cardinality at most ℓ have distinct closed in-neighborhoods within C. As far as we ... -
From Subkautz Digraphs to Cyclic Kautz Digraphs
Dalfó, Cristina (World Scientific Publishing, 2018)Kautz digraphs K(d, l) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz digraphs CK(d, l) were recently introduced by ...