Downloads provided by UsageCounts
arXiv: 1905.05083
handle: 10459.1/69197 , 2117/345607
Given an integer $\ell\ge 1$, a $(1,\le \ell)$-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 $k\geq2$, or minimum in-degree at least 3 and $k\geq1$, admits a $(1,\le \ell)$-identifying code with $\ell\leq2$, and in any case it does not admit a $(1,\le \ell)$-identifying code for $\ell\geq3$. 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.
05C69, 05C20, line digraph, Directed graphs (digraphs), tournaments, Classificació AMS::05 Combinatorics::05C Graph theory, dominating set, Grafs, identifying code, Dominating set, FOS: Mathematics, Mathematics - Combinatorics, Separating set, Teoria de, 1-factor, separating set, Grafs, Teoria de, Other types of codes, 1-Factor, Line digraph, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Identifying code, Combinatorics (math.CO), :05 Combinatorics::05C Graph theory [Classificació AMS], :Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]
05C69, 05C20, line digraph, Directed graphs (digraphs), tournaments, Classificació AMS::05 Combinatorics::05C Graph theory, dominating set, Grafs, identifying code, Dominating set, FOS: Mathematics, Mathematics - Combinatorics, Separating set, Teoria de, 1-factor, separating set, Grafs, Teoria de, Other types of codes, 1-Factor, Line digraph, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Graph theory, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Identifying code, Combinatorics (math.CO), :05 Combinatorics::05C Graph theory [Classificació AMS], :Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 37 | |
| downloads | 42 |

Views provided by UsageCounts
Downloads provided by UsageCounts