De-Bruijn Sequence -And Application in Graph theory.

Abstract

The goal of this paper is to introduce De Bruijn graphs and discuss their various applications. We will begin by examining N.G. de Bruijn's original paper and the proof of his claim that there are exactly 2^{2^(n-1)-n}  De Bruijn cycles in the binary De Bruijn graph B(2, n). In order to study this we explore the properties of Hamiltonian and Eulerian cycles that occur on De Bruijn graphs and the type of redundancy that occurs as a result. Lastly, in this paper we seek to provide some guidance into further research on De Bruijn graphs and their potential applications to other areas.