Comma-free Bipartite Subgraphs of the De Bruijn Graph

Abstract

By definition, the vertices of a de Bruijn graph are all strings of length $n-1$ ($n>1$) over a fixed finite alphabet. The edges are all strings of length $n$ over the same alphabet. The directed edge $a_1\dots a_n$ joins vertex $a_1\dots a_{n-1}$ to vertex $a_2\dots a_n$. A block code over an alphabet of $\sigma$ elements is comma-free if it does not contain any overlap of codewords. Representing the codewords of comma-free codes as directed edges of the de Bruijn graph, we give sufficient conditions that a bipartite subgraph of the de Bruijn graph whose underlying undirected graph is connected is a comma-free code.