Identifying Codes on Directed De Bruijn Graphs
Debra Boutin, Victoria Horan · 2014
For a directed graph G, a t-identifying code is a subset S ⊆ V (G) with the property that for each vertex v ∈ V (G) the set of vertices of S reachable from v by a directed path of length at most t is both non-empty and unique.A graph is called t-identifiable if there exists a t-identifying code.This paper shows that the de Bruijn graph B(d, n) is t-identifiable if and only if n ≥ 2t -1.It is also shown that a