The Research Of Several Transitive Graphs Based On Cayley Graphs

In the investigation of groups and graphs, graphs with some symmetry prop-erties have always been a hot topic. The symmetry of a graph mainly depends on its transitive property. We can get a graph which is vertex-transitive, half-transitive, arc-transitive or distance-transitive acting by its automorphism group. While in general, a graph usually doesn’t have these transitive properties. As par-ticular construction, the Cayley graph has become a typical representative in the investigation. In addition, based on the vertex-transitivity of the Cayley graph, it’s possible to investigate the half-transitive graphs and arc-transitive graphs on it. This is the main purpose of this thesis.The study of the normality of Cayley graphs is an important perspective in characterizing the symmetry of Cayley graphs. In Chapter Three of this thesis we study the Cayley graph of simple group A6. It is shown that except for22graphs, up to isomorphism, the connected non-arc-transitive Cayley graphs of A6of valency5are normal. Thus we get a complete classification of this kind of graphs.A graph is half-transitive if it is vertex-transitive, edge-transitive and non- arc-transitive. The study of half-transitive graphs was initiated by Tutte who proved that there are no half-transitive graphs with odd valency. From then on, the endless investigation of half-transitive graphs has been started. In Chapter Four, we consider the existence of half-transitive graphs of valency4of order p5. Then, we transform the problem to the investigation of half-transitive graphs of valency4on inner-abelian groups of order p5. Up to isomorphism, we solve the existence of half-transitive graphs of three types of the groups at last.We call a graph arc-transitive graph, also name it symmetric graph if the au-tomorphism group acts transitive on its arcs. Along with the study of arc-transitive graphs, it spreads to s-arc transitive graphs with some positive integer s. The study of s-arc-transitive graphs was also started with Tutte, who proved that there are no cubic s-transitive graphs when s is greater than six. Thus, we consider about1-regular Cayley graphs of valency6in Chapter Five and get results below:all of the1-regular Cayley graphs of valency6with nonabelian vertex stabilizer have core, thus we get a characterization of1-regular Cayley graphs of valency6.The method used in this thesis is mainly group-and-graph-theoretic. The concepts of groups and algebraic graph theory are referred to [1-3].