Back to search

University of Waterloo

Hamilton Paths in Generalized Petersen Graphs

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2002

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pensaert, William

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright: 2002, Pensaert, William. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1198

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pensaert, William. Hamilton Paths in Generalized Petersen Graphs. University of Waterloo, 2002. http://hdl.handle.net/10012/1198