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

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 $\mathcal{B}(d,n)$. It is shown that $\mathcal{B}(d,n)$ is $t$-identifiable whenever $d\ge 3$ and $n\ge 2t$, and $t\ge 1$. We also show that $\mathcal{B}(d,n)$ is $t$-identifiable if either $d\ge 3$, $n\ge 3$, and $t=2$, or if $d=2$, $n\ge 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$.

17 pages, 1 figure