A De Bruijn partial word of order n over a kary alphabet is a minimal length partial word such that every word of length n is compatible with factors of it. To construct such words, one can delete and add certain edges from a De Bruijn graph in such a way that a minimal length Eulerian path exists. We discuss in detail this technique, and also analyze the special cases of binary De Bruijn words with two holes as well as kary De Bruijn words with one hole; each of some order n.
Keywords: Combinatorics on Words; Graph Theory; Partial Words; De Bruijn Words.


