Arc-regular Graphs And Edge-tansitiye Covers

This thesis is devoted to study two important and relative topics in algebraic graph theory. One is regarding arc regular graphs, and the another is regarding regular covers of graphs.A graph is called arc regular if its full automorphism group is regular on its arc set. Arc regular graphs form an important family of symmetric graphs. It is well known that determining full automorphism groups of given graphs is one of the fundamental topics in algebraic graph theory and is gen-erally very difficult. Since arc regular graphs are tightly related to their full automorphism groups, they have received much attention in the literature, see [22,23,24,25,27,29,47,67,69,70,35,87]. A positive integer n is called square-free or cube-free if there is no prime p such that p2|n or p3|n respectively. It is proved in [98] that there is no cubic arc regular graph of order four times an odd square-free integer. In Chapter3, we extend this result to any prime valency:we prove that there exists no arc regular graph with order four times an odd square-free integer and any prime valency, and classify all X-arc-regular graphs of order four times an odd square-free in-teger and any prime valency which exactly consist of two infinite families of graphs. In Chapter4, a characterization of arc regular graphs of prime valency and order eight times an odd square-free integer, and certain new and interesting families of arc-regular graphs are founded.A typical method for studying transitive graphs is taking normal quo-tient graphs, aiming to reduce the study to investigate the correspond-ing’small’graphs. Then, characterizing transitive graphs can be divided into the following two steps:(1) characterizing corresponding’basic’graphs (that is, graphs with no nontrivial normal quotient graphs);(2) approach-ing regular covers or multi-covers of the obtained basic graphs. There-fore, characterizing regular graphs has been a very important topic in al-gebraic graph theory, and quite a lot of results have been obtained, see [2,11,12,30,43,48,60,61,63,66,68,92]. However, it should be not-ed that most results obtained are about regular covers of symmetric graphs with small order, and the results about regular covers of infinite families of graphs are rare. In [20,21], classifications of2-arc-transitive regular cover-s of complete graphs (with covering transformation groups being cyclic,Zp2or Zp3where p is a prime) are obtained. As typical symmetric graphs, com-plete graphs naturally appear as normal quotient graphs in the study of many families of graphs, characterizing their regular covers with ’weak’ symmetry would be an interest topic. In Chapter5, a characterization of edge-transitive regular cyclic covers of completed graphs with prime power order is given, and certain new families of graphs are constructed; moreover, by using volt-age assignment theory, arc transitive regular cyclic covers of the complete graph with order8are determined. In Chapter6, a complete classification of edge-transitive metacyclic regular covers of the Petersen graph is obtained; and as a application, it is proved that there is no cubic arc-regular graph of order5m, where m is a cube-free positive integer and coprime to15.