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 . . . . . .