On hamilton cycles and hamilton cycle decompositions of graphs based on groups

Dean, Matthew Lee Youle (2006). On hamilton cycles and hamilton cycle decompositions of graphs based on groups PhD Thesis, School of Physical Sciences, The University of Queensland.

       
Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
n01front_Dean.pdf n01front_Dean.pdf application/pdf 121.04KB 2
n02content_Dean.pdf n02content_Dean.pdf application/pdf 918.81KB 5
Author Dean, Matthew Lee Youle
Thesis Title On hamilton cycles and hamilton cycle decompositions of graphs based on groups
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
Publication date 2006
Thesis type PhD Thesis
Total pages 74
Collection year 2006
Subjects L
230101 Mathematical Logic, Set Theory, Lattices And Combinatorics
Abstract/Summary A Hamilton cycle is a cycle which passes through every vertex of a graph. A Hamilton cycle decomposition of a k-regular graph is defined as the partition of the edge set into Hamilton cycles if k is even, or a partition into Hamilton cycles and a 1-factor, if k is odd. Consequently, for 2-regular or 3-regular graphs, finding a Hamilton cycle decompositon is equilvalent to finding a Hamilton cycle. Two classes of graphs are studies in this thesis and both have significant symmetry. The first class of graphs is the 6-regular circulant graphs. These are a king of Cayley graph. Given a finite group A and a subset S ⊆ A, the Cayley Graph Cay(A,S) is the simple graph with vertex set A and edge set {{a, as}|a ∈ A, s ∈ S}. If the group A is cyclic then the graph is called a circulant graph. This thesis proves two results on 6-regular circulant graphs: 1. There is a Hamilton cycle decomposition of every 6-regular circulant graph Cay(Z[subscript n],S) in which S has an element of order n; 2. There is a Hamilton cycle decomposition of every connected 6-regular circulant graph of odd order. The second class of graphs examined in this thesis is a futher generalization of the Generalized Petersen graphs. The Petersen graph is well known as a highly symmetrical graph which does not contain a Hamilton cycle. In 1983 Alspach completely determined which Generalized Petersen graphs contain Hamilton cycles. In this thesis we define a larger class of graphs which includes the Generalized Petersen graphs as a special case. We call this larger class spoked Cayley graphs. We determine which spoked Cayley graphs on Abelian groups are Hamiltonian. As a corollary, we determine which are 1-factorable.

 
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 21 Nov 2008, 15:02:11 EST