The maximum independent sets of de Bruijn graphs of diameter 3

Details The maximum independent sets of de Bruijn graphs of diameter 3 The maximum independent sets of de Bruijn graphs of diameter 3

2009-05-23

arxiv.org/abs/0905.3820v2

Mathematics

Combinatorics

Updated version with a new title. Mostly a more clearly written version. The content is mostly the same as in the original ver

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The maximum independent sets of de Bruijn graphs of diameter 3 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The maximum independent sets of de Bruijn graphs of diameter 3, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The maximum independent sets of de Bruijn graphs of diameter 3 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499545