Arc-Transitive Graphs And Edge-Primitive Graphs

Using group theory, specially permutation group to study the structure of the graph is an important approach in algebraic graph theory, and the symmetry of graphs is a major research topic, which is mainly described by the actions of the full automorphism groups of graphs. Let X be a finite, simple and undirected graph. For a positive integer s, an s-arc in a graph is an ordered (s+1)-tuple (υ0, υ1,…,υs-1, υs) of vertices of the graph X such that υi-1is adjacent to υi for1≤i≤s, and υi-1≠υi+1for1≤i≤s-1. A graph X is said to be s-arc-transitive or s-regular if Aut(X) is transitive or regular on the set of s-arcs in X, respectively. In particular,1-arc-transitive is simply called arc-transitive. An s-arc-transitive graph is said to be s-transitive if it is not (s+1)-arc-transitive. A graph X is said to be edge-primitive if Aut(X) is primitive on the edge set. This thesis mainly investigates arc-transitive graphs and edge-primitive graphs.Chapter Ⅰ is an introduction part. We introduce some basic definitions of group theory and algebraic graph theory, the relative background of our research and main works.Chapter Ⅱ investigates the automorphism groups of arc-transitive graphs of prime valency. First in Section1we give some preliminary results. In Section2, we give the exact structure of solvable vertex stabilizers of prime-valent arc-transitive graphs. In Section3, we determine the structure of vertex stabilizers of pentavalent arc-transitive graphs.Weiss in1973determined all cubic edge-primitive graphs. In Chapters Ⅲ and Ⅳ, we give the complete classifications of tetravalent or pentavalent edge-primitive graphs, respectively. Chapter Ⅲ classifies tetravalent edge-primitive graphs. It is shown that, up to iso-morphism, there are six such graphs, that is, the complete graph K5, the co-Heawood graph of order14, the complete bipartite graph-K4,4, and three coset graphs defined on Aut(PSL(3,3)), Aut(M12) and Aut(G2(3)), respectively.Chapter Ⅳ classifies pentavalent edge-primitive graphs. It is shown that, up to isomorphism, there are five sporadic graphs and two infinite families, that is, the complete graph K6, the complete bipartite graph K5,5, three coset graphs defined on Aut(PSL(3,4)), Aut(J3) and Aut(PSp(4,4)) respectively, and two infinite families of coset graphs defined on PSL(2,p) and PGL(2,p) respectively.Chapter Ⅴ investigates classifications of arc-transitive graphs of small valency. Let p be a prime. In Section1we give some preliminary results. In Section2, we classify con-nected tetravalent arc-transitive graphs of order9p. It is shown that, up to isomorphism, there are five sporadic graphs and three infinite families, of which two are1-transitive graphs of order18, one is1-transitive normal Cayley graph on the non-abelian group of order27, two are vertex-primitive coset graphs on Aut(A6) and PSL(2,17), one is an in-finite family of1-regular normal Cayley graphs on Z8p, and two are infinite families of1-regular normal Cayley graphs on Z3×Z3p. In Section3, we classifiy connected tetrava-lent arc-transitive graphs of order3p2. It is shown that, up to isomorphism, there are four sporadic graphs and three infinite families, of which two are graphs of order12, two are normal Cayley graphs on groups of order27, and three are infinite families of1-regular normal Cayley graphs on groups of order3p2. In Section4, a complete classification of connected pentavalent arc-transitive graphs of order12p is given. As a result, a connected pentavalent arc-transitive graph of order12p exists if and only if p=2,3,5or11, and up to isomorphism, there are only nine such graphs:one for each p=2,3and5, and six for p=11.