Edge-Disjoint Hamiltonian Cycles in De Bruijn Graphs

Honors College Thesis

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/honors_college_theses/xk81jn17x

Descriptions

Attribute Name	Values
Creator	Lytle, Megan E.
Abstract	The purpose of this thesis is to examine the number of edge-disjoint Hamiltonian cycles in de Bruijn graphs using ideas from finite field theory, particularly linear recurring sequences. It is known that the de Bruijn graph B(d,n) admits d-1 disjoint Hamiltonian cycles when d is a power of 2, and it is conjectured that all de Bruijn graphs B(d,n) admit d-1 disjoint Hamiltonian cycles. The conjecture also states that for every de Bruijn graph there exists a Hamiltonian cycle to which a particular function, defined in chapter 4, can be applied to obtain d-2 additional Hamiltonian cycles. I have shown for several specific de Bruijn graphs that this method does not work on Hamiltonian cycles obtained using linear recurring sequences. Keywords: de Bruijn graphs, Hamiltonian cycles, interconnection networks, linear recurring sequences
Resource Type	Honors College Thesis
Date Available	2013-07-10T23:11:30+00:00
Date Issued	2013-06-06
Degree Level	Bachelor's
Degree Name	Honors Bachelor of Science (H.B.S.)
Degree Field	Mathematics
Degree Grantor	Oregon State University
Commencement Year	2013
Advisor	Flahive, Mary
Non-Academic Affiliation	Oregon State University. Honors College
Rights Statement	In Copyright
Publisher	Oregon State University
Peer Reviewed	No
Language	English [eng]
Replaces	http://hdl.handle.net/1957/40261

Parents:

This work has no parents.

In Collection:

Thumbnail	Title	Date Uploaded	Visibility	Actions
	FINALTHESIS_Megan_Lytle.pdf	2017-07-29	Public	Download