Identifying codes in line digraphs

DOI10.1016/J.AMC.2020.125357zbMATH Open1462.05268arXiv1905.05083OpenAlexW3026136084MaRDI QIDQ2189840FDOQ2189840

Authors: C. Dalfó, Berenice Martínez-Barona, C. Balbuena 

Publication date: 17 June 2020

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: Given an integer $ellge1$, a $(1,leell)$-identifying code in a digraph is a dominating subset $C$ of vertices such that all distinct subsets of vertices of cardinality at most $ell$ 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 $kgeq2$, or minimum in-degree at least 3 and $kgeq1$, admits a $(1,leell)$-identifying code with $ellleq2$, and in any case it does not admit a $(1,leell)$-identifying code for $ellgeq3$. 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.

Full work available at URL: https://arxiv.org/abs/1905.05083

Recommendations

• Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code
• Characterizing identifying codes from the spectrum of a graph or digraph
• Identifying codes in line graphs
• On the minimum size of an identifying code over all orientations of a graph
• Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets

zbMATH Keywords

dominating setidentifying codeline digraph1-factorseparating set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Other types of codes (94B60)

Cites Work

• On a new class of codes for identifying vertices in graphs
• Identifying codes in line graphs
• Line Digraph Iterations and the (d, k) Digraph Problem
• Title not available (Why is that?)
• Optimal identification of sets of edges using 2-factors
• On the linegraph of a directed-graph
• Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• A linear algorithm for minimum 1-identifying codes in oriented trees
• Connection digraphs and second-order line digraphs
• Characterizing identifying codes from the spectrum of a graph or digraph

Cited In (9)

• Identifying codes in line graphs
• Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
• Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code
• Characterizing identifying codes from the spectrum of a graph or digraph
• Partial linear spaces and identifying codes
• On the minimum size of an identifying code over all orientations of a graph
• A linear algorithm for minimum 1-identifying codes in oriented trees
• Identifying codes on directed de Bruijn graphs
• Edge identifying codes

This page was built for publication: Identifying codes in line digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189840)