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.
| Identifer | oai:union.ndltd.org:ADTP/289851 |
| Creators | Dean, Matthew Lee Youle |
| Source Sets | Australiasian Digital Theses Program |
| Detected Language | English |
Page generated in 0.0018 seconds