Symmetric Graphs Of Small Valency

A graph is symmetric(or arc-transitive)if its automorphism group is transitive on the arc set of the graph.Symmetric graphs,especially symmetric graphs of small va-lency,are often used to design interconnection networks.This thesis investigates core-free cubic m-Cayley graphs,tetravalent 2-arc-transitive Cayley graphs over non-abelian simple groups,pentavalent symmetric graphs admitting vertex-transitive non-abelian simple groups and pentavalent symmetric graphs admitting transitive non-abelian char-acteristically simple groups.This thesis is organized as follows.Chapter 1 introduces some basic definitions of finite group theory and graph theory.Chapter 2 investigates connected core-free cubic symmetric m-Cayley graphs.A graph ’ is called an m-Cayley graph over G if Aut(Γ)has an automorphism group G which acts semiregular on V(Γ)with m orbits.1-Cayley graphs are the well known Cayley graphs and 2-Cayley graphs also called bi-Cayley graphs.In this chapter,we investigate properties of connected cubic symmetric m-Cayley graphs and use these to develop a computational method for classifying connected core-free cubic symmetric m-Cayley graphs,with the help of the MAGMA system.Our computational approach gives a new proof of the classification of connected core-free cubic symmetric Cay-ley graphs(with 15 in total,and with 2 being Cayley graphs over non-abelian simple groups).But also we take this much further.In the case m = 2 we use it to show there are exactly 109 connected core-free cubic symmetric bi-Cayley graphs,48 of which are over some non-abelian simple groups.Also in the cases m = 3,4,5,6 and 7 we find there are 1,6,81,462 and 3267 connected core-free cubic 1-arc-regular m-Cayley graphs,respectively.Chapter 3 investigates tetravalent 2-arc-transitive Cayley graphs over non-abelian simple groups.Let ’ be a Cayley graph ’ over the group G.The graph Γ is called normal if G is normal in the full automorphism group Aut(Γ)of Γ.Let G be a finite non-abelian simple group and let Γ be a connected tetravalent 2-arc-transitive Cayley graph over G.In this chapter,we proved that either Γ is a normal Cayley graph over G,or G is one of 7 possible candidates and Aut(Γ)has a normal arc-transitive non-abelian simple subgroup T such that G ≤T and(G,T)=(M11,M12)or(An-1,An)with n = 23 · 3,22 · 32,23 · 32,24 · 32,24 · 33 or 24 · 36.Chapter 4 focuses on connected pentavalent symmetric graphs admitting vertex-transitive non-abelian simple groups.Let G be a finite non-abelian simple group and letΓ be a connected pentavalent symmetric graph such that G≤Aut(Γ).In this chapter,we show that if G is transitive on the vertex set of Γ,then either G(?)Aut(Γ)or Aut(Γ)contains a non-abelian simple normal subgroup T such that G≤T and(G,T)is one of 58 possible pairs of non-abelian simple groups.In particular,if G is arc-transitive,then(G,T)is one of 17 possible pairs,and if G is regular on the vertex set of Γ,then(G,T)is one of 13 possible pairs.Chapter 5 gives a characterization of connected pentavalent symmetric graphs ad-mitting characteristically vertex-transitive non-abelian simple groups.Let G be a finite non-abelian simple group and n be a positive integer.Let Γ be a pentavalent symmetric G-vertex-transitive graph and ∑ be a pentavalent symmetric Gn-vertex-transitive graph.In this chapter,we prove that if G(?)Aut(Γ),then Gn(?)Aut(∑).This result,among the result in Chapter 4,implies that:1)for every connected pentavalent symmetric Gn-vertex-transitive graph ∑,either Gn is normal in Aut(∑)or G is one of 57 simple groups,that is,PSL(2,8),Ω8-(2)or An-1 with n≥6 and n | 29 · 32 · 5;2)every connected pentavalent symmetric Cayley graph ∑ over Gn is normal except G is one of 20 simple groups,that is,PSL(2,8),Ω8-(2)or An-1 with n = 2 · 3,23,32,2 · 5,22 · 3,22 · 5,23 · 3,23·5,2·3.5,24·5,23·3.5,24·32·5,26·3·5,25·32.5,27·3.5,26·32.5,27.32·5or 29 · 32 · 5;3)for every connected pentavalent G"-symmetric graph Σ,either Gn is normal in Aut(Σ)or G is one of 17 simple groups,that is,An-1 with n = 2 · 3,22 · 3,24,23 · 3,25,22·32,24·3,23·32,25·3,24·32,26·3,25·32,27·3,26·32,27 · 32,28 · 32 or 29·32.In Chapter 6,we discuss some problems to be solved.