Honors College Thesis

 

Edge-Disjoint Hamiltonian Cycles in De Bruijn Graphs Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/honors_college_theses/xk81jn17x

Descriptions

Attribute NameValues
Creator
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.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Non-Academic Affiliation
Rights Statement
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Submitted by Kassena Hillman (kassena.hillman@oregonstate.edu) on 2013-06-27T21:45:45ZNo. of bitstreams: 1FINALTHESIS Megan Lytle.pdf: 229092 bytes, checksum: d3b6e42a37e91c3d6a851f8977be8ab5 (MD5)
  • description.provenance : Made available in DSpace on 2013-07-10T23:11:30Z (GMT). No. of bitstreams: 1FINALTHESIS Megan Lytle.pdf: 229092 bytes, checksum: d3b6e42a37e91c3d6a851f8977be8ab5 (MD5)
  • description.provenance : Approved for entry into archive by Deanne Bruner(deanne.bruner@oregonstate.edu) on 2013-07-10T23:11:30Z (GMT) No. of bitstreams: 1FINALTHESIS Megan Lytle.pdf: 229092 bytes, checksum: d3b6e42a37e91c3d6a851f8977be8ab5 (MD5)

Relationships

Parents:

This work has no parents.

In Collection:

Items