E-Book Content
CAYLEY GRAPH ENUMERATION
by
Marni Mishna BMath, University of Waterloo, 1998.
T HESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF
M ASTER OF S CIENCE IN THE DEPARTMENT OF
M ATHEMATICS &S TATISTICS
c Marni Mishna 2003 SIMON FRASER UNIVERSITY March 2000 All rights reserved. This work may not be reproduced in whole or in part, by photocopy or other means, without permission of the author.
APPROVAL Name:
Marni Mishna
Degree:
Master of Science
Title of Thesis:
Cayley Graph Enumeration
Examining Committee:
Dr. R. Lockhart (Chair)
Dr. B. Alspach Senior Supervisor
Dr. T. C. Brown
Dr. P. Hell
Dr. B. Stevens External Examiner
Date Approved:
March 3, 2000
ii
Abstract Pólya’s Enumeration Theorem is a powerful method for counting distinct arrangements of objects. J. Turner noticed that circulant graphs have a sufficiently algebraic structure that Pólya’s theorem can be used to determine the number of non-isomorphic circulants of order for prime . Recent results on CI-groups suggest that Turner’s method can be used to enumerate a larger collection of circulants, circulant digraphs, and Cayley graphs and
digraphs on and .
iii
Acknowledgments Brian Alspach found me a nice enumeration problem and carefully read the work. NSERC and SFU provided me with the financial support that allowed this to be a quick project. Big huge thanks to the wonderful, fun people that I have met while in Vancouver. I have been enlightened, entertained and inspired. I will leave here a better person than when I arrived. Karen Meagher and Adam Fraser, my best friends, have continued to tolerate, support and encourage me. Karen offered some real killer suggestions and actually read the whole thing. This one goes out to my family, especially my mom who even tried to understand what it meant.
it’s an automatic toaster! brews delicious coffee automatically! does any mixing job! by solving complex mathematical formulas
iv
Contents
Approval
ii
Abstract
iii
Acknowledgments
iv
Contents
v
List of Tables
vii
List of Figures
viii
1 Introduction
1
1.1
Definitions and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
CI-Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Some Known CI-Groups . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2 Circulants of Prime Order
5
2.1
Determining the Cycle Index . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2
Enumerating Circulants of Prime Order . . . . . . . . . . . . . . . . . . .
12
v
CONTENTS
vi
2.3
Circulant Digraphs of Prime Order . . . . . . . . . . . . . . . . . . . . . .
14
2.4
Counting Regular Cayley Graphs . . . . . . . . . . . . . . . . . . . . . . .
15
3 Circulants and Circulant Digraphs
18
3.1
Circulants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.2
Circulant Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4 Unit Circulants
28
4.1
Odd Prime Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.2
Products of Odd Prime Powers . . . . . . . . . . . . . . . . . . . . . . . .
31
4.3
Unit Circulants of All Orders . . . . . .