Half-arc-transitive Graph And Half-edge-transitive Graph

The thesis investigates the application of group theory on graph theory. The main results are investigation of half-arc-transitive graphs, half-edge-transitive graphs and non-normal Cayley graphs.Chapter 1 introduces some basic definitions of group theory and graph theory, main results and relative background of the research.Chapter 2,3,4 investigate tetravalent half-arc-transitive graphs. A graph X is called half-arc-transitive graph if the full automorphism group of X is transitive on ver-tex set and edge set, but not arc set. Let p, q, r be distinct odd primes. In Chapter 2, we prove that there exists no tetravalent half-arc-transitive graphs of order 2p2. In Chap-ter 3, we determine the classification of tetravalent half-arc-transitive graphs of order 2pq. Contrary to the tetravalent half-arc-transitive graphs of order 4p, there are two infinite families of tetravalent half-arc-transitive graphs of order 2pq, of which one is Cayley and the other is non-Cayley. Furthermore, for given odd primes p and q, up to isomorphic, the number of the tetravalent half-arc-transitive graphs of order 2pq is de-termined. In Chapter 4, we determine the classification of tetravalent half-arc-transitive graphs of order p2q and pqr, and prove that tetravalent half-arc-transitive graphs of order p2q and pqr are normal Cayley graphs. In particular, there exist some infinite families of tetravalent half-arc-transitive graphs of order p2q with solvable automor-phism groups which are non-metacirculant graphs. Feng et al. proved that tetravalent half-arc-transitive graphs of order 4p are non-Cayley and Xu determined the tetravalent half-arc-transitive graphs of order p3. Combines with the above results, we classify and enumerate the tetravalent half-arc-transitive graphs of order a product of three primes.Chapter 5 investigates the 2q-valent half-arc-transitive graphs of order 4p, where q is an odd prime. We prove that 2q-valent half-arc-transitive graphs of order 4p are normal Cayley graphs on metacyclic groups, which exists if and only if 4q|p-1. Furthermore, such a graph is unique for a given order. Chapter 6 investigates half-edge-transitive graphs and non-normal Cayley graphs. A graph X is called half-edge-transitive graph if the full automorphism group is tran-sitive on vertex set and has two orbits with the same length both on edge set and arc set. First, we give a sufficient condition of tetravalent half-edge-transitive graphs and non-normal Cayley graphs. Based on the sufficient condition, we construct some infi-nite families non-normal Cayley graphs on alternating group An, which are half-edge-transitive. These examples show that there exist infinite families of tetravalent non-normal Cayley graphs on non-abelian simple groups. Similar to the tetravalent half-arc-transitive graphs and tetravalent symmetric graphs, tetravalent half-edge-transitive graphs can have arbitrary large stabilizers. Mingyao Xu et. al proved that there are only four tetravalent non-normal Cayley graphs on alternating group A5, which are half-edge-transitive graphs and which are the first known construction for the tetravalent non-normal Cayley graphs on non-abelian simple groups. In this chapter, we prove that there are two tetravalent non-normal Cayley graphs on alternating group A6, which are half-edge-transitive graphs.