Return to search

De Bruijn Graphs and Lamplighter Groups

De Bruijn graphs were originally introduced for finding a superstring representation for all fixed length words of a given finite alphabet. Later they found numerous applications, for instance, in DNA sequencing. Here we study a relationship between de Bruijn graphs and the family of lamplighter groups (a particular class of wreath products). We show how de Bruijn graphs and their generalizations can be presented as Cayley and Schreier graphs of lamplighter groups.

Identiferoai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/38832
Date20 February 2019
CreatorsAlharthy, Shathaa
ContributorsKaimanovich, Vadim
PublisherUniversité d'Ottawa / University of Ottawa
Source SetsUniversité d’Ottawa
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Formatapplication/pdf

Page generated in 0.0018 seconds