Self-Complementary Arc-Transitive Graphs and Their Imposters

algebraic graph theory;self-complementary arc-transitive graphs;Combinatorics and Optimization

Mullin, Natalie

University of Waterloo

关键词: algebraic graph theory;    self-complementary arc-transitive graphs;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4264/1/nm_thesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

This thesis explores two infinite families of self-complementary arc-transitive graphs: the familiar Paley graphs and the newly discovered Peisert graphs. After studying both families, we examine a result of Peisert which proves the Paley and Peisert graphs are the only self-complementary arc transitive graphs other than one exceptional graph. Then we consider other families of graphs which share many properties with the Paley and Peisert graphs. In particular, we construct an infinite family of self-complementary strongly regular graphs from affine planes. We also investigate the pseudo-Paley graphs of Weng, Qiu, Wang, and Xiang. Finally, we prove a lower bound on the number of maximal cliques of certain pseudo-Paley graphs, thereby distinguishing them from Paley graphs of the same order.