The maximum independent sets of de Bruijn graphs of diameter 3 (Q640456)

Summary: 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.