Hamilton decompositions of 6-regular Abelian Cayley graphs.

摘要

In 1969, Lovasz asked whether every connected, vertex-transitive graph has a Hamilton path. This question has generated a considerable amount of interest, yet remains vastly open. To date, there exist no known connected, vertex-transitive graph that does not possess a Hamilton path. For the Cayley graphs, a subclass of vertex-transitive graphs, the following conjecture was made:;Weak Lovasz Conjecture: Every nontrivial, finite, connected Cayley graph is hamiltonian.;The Chen-Quimpo Theorem proves that Cayley graphs on abelian groups flourish with Hamilton cycles, thus prompting Alspach to make the following conjecture:;Alspach Conjecture: Every 2k-regular, connected Cayley graph on a finite abelian group has a Hamilton decomposition.;Alspach's conjecture is true for k = 1 and 2, but even the case k = 3 is still open. It is this case that this thesis addresses.;Chapters 1--3 give introductory material and past work on the conjecture. Chapter 3 investigates the relationship between 6-regular Cayley graphs and associated quotient graphs. A proof of Alspach's conjecture is given for the odd order case when k = 3. Chapter 4 provides a proof of the conjecture for even order graphs with 3-element connection sets that have an element generating a subgroup of index 2, and having a linear dependency among the other generators.;Chapter 5 shows that if Gamma = CAY(A, {s1, s2, s3}) is a connected, 6-regular, abelian Cayley graph of even order, and for some 1 ≤ i ≤ 3, Delta i = CAY (A/⟨s i⟩, { sj1,sj2 }) is 4-regular, and Deltai ≃ / CAY( Z3 , {1, 1}), then Gamma has a Hamilton decomposition. Alternatively stated, if Gamma = CAY(A, S) is a connected, 6-regular, abelian Cayley graph of even order, then Gamma has a Hamilton decomposition if S has no involutions, and for some s ∈ S, CAY(A/⟨ s⟩, S¯) is 4-regular, and of order at least 4.;Finally, the Appendices give computational data resulting from C and MAGMA programs used to generate Hamilton decompositions of certain non-isomorphic Cayley graphs on low order abelian groups.