  A de Bruijn sequence of order n over a k-symbol alphabet is a circular
sequence where each length-n sequence occurs exactly once. We present a way of
extending de Bruijn sequences by adding a new symbol to the alphabet: the
extension is performed by embedding a given de Bruijn sequence into another one
of the same order, but over the alphabet with one more symbol, while ensuring
that there are no long runs without the new symbol. Our solution is based on
auxiliary graphs derived from the de Bruijn graph and solving a problem of
maximum flow.
