2014/12/18 by Boutin, Debra, Goliber, Victoria Horan, Pelto, Mikko
#05C69 (primary) #94B25 (secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1412.5842
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 \it 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 t-identifying code for t-identifiable de~Bruijn graphs must contain at least dn-1(d-1) vertices, and constructions are given to show that this lower bound is achievable n ≥ 2t. Further a (possibly) non-optimal construction is given when n=2t-1. Additionally, with respect to B(d,n) we provide upper and lower bounds on the size of a minimum t-dominating set (a subset with the property that every vertex is at distance at most t from the subset), that the minimum size of a directed resolving set (a subset with the property that every vertex of the graph can be distinguished by its directed distances to vertices of S) is dn-1(d-1), and that if d>n the minimum size of a \it determining set (a subset S with the property that the only automorphism that fixes S pointwise is the trivial automorphism) is \lceil (d-1)/(n)\rceil.