On the Existence of t-Identifying Codes in Undirected De Bruijn Graphs

Original · EN

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.