Enumeration, isomorphism and Hamiltonicity of Cayley graphs: 2-generated and cubic.
详细信息
- 作者：Effler ; Scott Michael.
- 学历：Master
- 年：2002
- 导师：Ruskey, Frank
- 毕业院校：University of Victoria
- 专业：Computer Science.
- ISBN：0612749568
- CBH：MQ74956
- Country：Canada
- 语种：English
- FileSize：3148771
- Pages：104
文摘
This thesis explores 2-generated and cubic Cayley graphs. All 2-generated Cayley graphs with generators from Sn , where n ≤ 9, were generated. Further, 3-generated cubic Cayley graphs, where n ≤ 7, were also generated. Among these, the cubic Cayley graphs with up to 40320 vertices were tested for various properties including Hamiltonicity and diameter. These results are available on the internet in easy to read tables. The motivation for the testing of Cayley graphs for Hamiltonicity was the conjecture that states that every connected Cayley graph is Hamiltonian.;New enumeration results are presented for various classes of 2-generated Cayley graphs. Previously known enumeration results are presented for cubic Cayley graphs.;Finally, isomorphism and color isomorphism of 2-generated and cubic Cayley graphs is explored. Numerous new results are presented.;All algorithms used in this thesis are explained in full.