Comma-free Bipartite Subgraphs of the De Bruijn Graph

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\ldots a_n\) joins vertex \(a_1\ldots a_{n-1}\) to vertex \(a_2\ldots 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.