This thesis puts forward the conjecture that for <i>n</i> > 3<i>k</i> with <i>k</i> > 2, the generalized Petersen graph, <i>GP</i>(<i>n,k</i>) is Hamilton-laceable if <i>n</i> is even and <i>k</i> is odd, and it is Hamilton-connected otherwise. We take the first step in the proof of this conjecture by proving the case <i>n</i> = 3<i>k</i> + 1 and <i>k</i> greater than or equal to 1. We do this mainly by means of an induction which takes us from <i>GP</i>(3<i>k</i> + 1, <i>k</i>) to <i>GP</i>(3(<i>k</i> + 2) + 1, <i>k</i> + 2). The induction takes the form of mapping a Hamilton path in the smaller graph piecewise to the larger graph an inserting subpaths we call <i>rotors</i> to obtain a Hamilton path in the larger graph.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/1198 |
| Date | January 2002 |
| Creators | Pensaert, William |
| Publisher | University of Waterloo |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | application/pdf, 183802 bytes, application/pdf |
| Rights | Copyright: 2002, Pensaert, William. All rights reserved. |
Page generated in 0.0016 seconds