Edge-Disjoint Hamiltonian Cycles in De Bruijn Graphs Public Deposited

http://ir.library.oregonstate.edu/concern/undergraduate_thesis_or_projects/xk81jn17x

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Advisor
Non-Academic Affiliation
Keyword
Rights Statement
Language
Replaces
Additional Information
  • description.provenance : Submitted by Kassena Hillman (kassena.hillman@oregonstate.edu) on 2013-06-27T21:45:45Z No. of bitstreams: 1 FINALTHESIS 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: 1 FINALTHESIS Megan Lytle.pdf: 229092 bytes, checksum: d3b6e42a37e91c3d6a851f8977be8ab5 (MD5)
  • description.provenance : Made available in DSpace on 2013-07-10T23:11:30Z (GMT). No. of bitstreams: 1 FINALTHESIS Megan Lytle.pdf: 229092 bytes, checksum: d3b6e42a37e91c3d6a851f8977be8ab5 (MD5)

Relationships

In Administrative Set:
Last modified: 07/28/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items