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

MaRDI QIDQ6264156zbMATH OpenFDO

Authors Victoria Horan

Publication date 3 August 2015

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial codes (94B25)

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 $mathcalB(d,n)$. It is shown that $mathcalB(d,n)$ is $t$-identifiable whenever $dgeq3$ and $ngeq2t$, and $tgeq1$. We also show that $mathcalB(d,n)$ is $t$-identifiable if either $dgeq3$, $ngeq3$, and $t=2$, or if $d=2$, $ngeq3$, and $t=1$. The remaining cases remain open. Additionally, we show that the eccentricity of the undirected non-binary de Bruijn graph is $n$.

This page was built for publication: On the Existence of $t$-Identifying Codes in Undirected De Bruijn Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6264156)