2015/08/03 by Horan, Victoria
#05C69 (primary) #94B25 (secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1508.00403
This paper proves the existence of t-identifying codes on the class of undirected de Bruijn graphs with string length n and alphabet size d, referred to as B(d,n). It is shown that B(d,n) is t-identifiable whenever d ≥ 3 and n ≥ 2t, and t ≥ 1. We also show that B(d,n) is t-identifiable if either d ≥ 3, n ≥ 3, and t=2, or if d = 2, n ≥ 3, and t=1. The remaining cases remain open. Additionally, we show that the eccentricity of the undirected non-binary de Bruijn graph is n.