 Identifying codes in line digraphsC. Balbuena, C. Dalfó and B. Martínez-Barona Applied Mathematics and Computation, 2020, vol. 383, issue C 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 minimum 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. Keywords: Line digraph; Identifying code; Dominating set; Separating set; 1-Factor (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:383:y:2020:i:c:s0096300320303210 DOI: 10.1016/j.amc.2020.125357 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.