Covering the de Bruijn graph

A subset S of maximally independent vertices from the de Bruijn graph B n is a cover of B n if every vertex of B n − S is adjacent to some vector of S . We find bounds on the size of a cover and algorithms and constructions to achieve those bounds.