2019/05/13 by C. Balbuena, Balbuena, C., C. Dalfó +3
Computer Science · Engineering · #05C20 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · doi:10.48550/arxiv.1905.05083
openalex publication_date 2019/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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-neighbourhood within C. In this paper, we prove that every k-iterated line digraph of minimum in-degree at least 2 and k≥2, or minimum in-degree at least 3 and k≥1, admits a (1,≤ ℓ)-identifying code with ℓ≤2, and in any case it does not admit a (1,≤ ℓ)-identifying code for ℓ≥3. Moreover, we find that the identifying number of a line digraph is lower bounded by the size of the original digraph minus its order. Furthermore, this lower bound is attained for oriented graphs of minimum in-degree at least 2.