On the Existence of t-Identifying Codes in Undirected De Bruijn Networks
Victoria Horan · arXiv (Cornell University) · 2015
Abstract : 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 is greater than or equal to 3 and n is greater than or equal to 2t, and t is greater than or equal to 1, or d is greater than or equal to 3, n is greater than or equal to 3, and t = 2, or d = 2, n is greater than or equal to 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.