2009/05/23 by Dustin A. Cartwright, Dustin Cartwright, Maria Angelica Cueto +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05A15 #05C69 #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #math.CO #msc:05A15 #msc:05C69
paper · pdf · doi:10.48550/arxiv.0905.3820
Updated version with a new title. Mostly a more clearly written version. The content is mostly the same as in the original version. 18 pages, 1 figure, 1 table
openalex publication_date 2009/05/23 · arxiv created 2010/09/28 · arxiv updated 2010/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The nodes of the de Bruijn graph B(d,3) consist of all strings of length 3, taken from an alphabet of size d, with edges between words which are distinct substrings of a word of length 4. We give an inductive characterization of the maximum independent sets of the de Bruijn graphs B(d,3) and for the de Bruijn graph of diameter three with loops removed, for arbitrary alphabet size. We derive a recurrence relation and an exponential generating function for their number. This recurrence allows us to construct exponentially many comma-free codes of length 3 with maximal cardinality.