Classifications And Enumerations Of Several Families Of Symmetric Graphs

The thesis investigates the application of group theory on graph theory, whose subjects are graphs with some symmetric property, and whose main method ap-plies its automorphism group of a graph on its symmetries. The main results are classifications and enumerations of several families of symmetric graphs.Chapter 1 introduces some basic definitions of group theory and graph theory, the main results and relative background of the research.Chapter 2 gives a classification and enumeration of one-regular Cayley graphs of any prime valency on a dihedral group. A graph is one-regular if its automor-phism group acts regularly on its arc sets. It is shown that for an odd prime q, there exists a q-valent one-regular Cayley graph on the dihedral group of order 2m if and only if m=qtp1e1p1e2…pses with m≥13, where t≤1,s≥1,ei≥1 and pi's are distinct primes such that q|(pi-1). There are exactly (q-1)s-1 non-isomorphic such graphs for a given order, which are explicitly constructed. Furthermore, it is shown that q-valent one-regular graphs of square-free orders are Cayley graph on dihedral groups, and as an application of the above result, q-valent one-regular graphs of square-free orders are classified and enumerated.Chater 3 gives a classification of cubic graph of order 4p. A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. Let p be a prime. Xu et al. [Chin. Ann. Math.B,25 (2004),545-554] classified the connected cubic symmetric graphs of order 4p. This chapter gives a classification of connected cubic vertex-transitive graphs of order 4p. As a result, the number of pairwise non-isomorphic connected cubic vertex-transitive graph of order 4p is 2 for p=2,4 for p=3,8 for p=5,6 for p=7,5+p-3/2 for p≥11 with 4|(p-1) and 3+p-3/2 for p≥11 with 4|(p-1).Chapter 4 investigates the symmetric graph of order 2pn of valency 5. A graph is symmetric if its automorphism group acts transitively on its arcs of the graph. Let p be a prime and let n>1 be integer. Then a symmetric graph of order 2pn of valency 5 is a normal cover of one of the following graphs:K6, K5,5, G(2p,5), V16, Q5, Cp21, Cp22, Cp3, and Cp4. As an application, symmetric graph of order 2p2 of valency 5 are classified. Chapters 5 gives a classification of arc-transitive regular Zn-cover of the com-plete graph K5 of order 5. It is shown that X is connected arc-transitive Zn-cover of K5 if and only if X is isomorphic to one of the following graphs:one-regular graph CC(5n, H) (n≠2), where H is a cyclic subgroup containing -1 of order 4 in Z5n*; 2-arc transitive graph CC(10,Z10*) ((?)K5,5-5K2); 1-arc transitive graph AC(5k,5,w), where k≤2; one-regular graph AC(5k,5,w), where k≥3 and w2≡-1(mod k). Such graphs are pairwise non-isomorphic.