Decomposition of de bruijn graphs

Abstract

A subset S of the vertices of a de Bruijn graph is called a sliding set if for each α in S there exist two elements β, τ in S such that αβ and βτ are directed edges of the de Bruijn graph. In this paper, some properties of sliding sets are obtained and it is shown that a de Bruijn graph can be decomposed as a union of sliding sets.

Keywords:

• De Bruijn Graph
• sliding set
• symmetric group