Generalized Cayley Graphs Over Cyclic Groups

The symmetry of graphs is a hot topic in algebraic graph theory,and has been extensively studied in the literature.This thesis mainly focuses on several classes of highly symmetrical graphs:vertex-transitive graph,Cayley graph,generalized Cayley graph etc.A graph is said to be vertex-transitive if its automorphism group is transitive on its vertex set.A graph is said to be a Cayley graph over a group H if it admits H as a group of automorphisms acting regularly on its vertex set.As a generalization of Cayley graph,in 1992,Maru?ic et al.introduced the so-called generalized Cayley graph.Let G be a finite group,S a subset of G and α an automorphism of G such that α2=1.The generalized Cayley graph X:=GC(G,S,α)on G with respect to the ordered pair(S,α)is the graph with vertex set G,with two vertices f,g∈V(X)being adjacent in X if and only if α(f-1)g∈S.By the definition,every Cayley graph is a generalized Cayley graph.The converse,however,is not true.As pointed out by Maru?ic et al.,the line graph of the Petersen graph is such a counter example.Nevertheless,it is also quite interesting to seek infinite families of generalized Cayley graph which are vertex-transitive but nonCayley.In 2015,Hujdurovic et al.constructed the first two infinite families of generalized Cayley graphs which are vertex-transitive but non-Cayley,and their graphs are 5-valent generalized Cayley graphs over cyclic groups of order 4a(a an odd integer).This thesis mainly considers generalized Cayley graphs over cyclic groups.We first study vertextransitivity and Cayley property of the generalized Cayley graphs over cyclic groups of prime power order,and in particular,we prove that generalized Cayley graphs over cyclic groups of prime power order must be Cayley graphs.Secondly,we give a classification of vertex-transitive but non-Cayley generalized Cayley graphs over cyclic groups of order 4a(a an odd integer)and valency at most 5.This thesis is organized as follows:In Chapter 1,we introduce the background and some basic problems on the generalized Cayley graphs,and then states our main results.In Chapter 2,we give some basic definitions and preliminary results of finite group theory and graph theory.In Chapter 3,we firstly consider the generalized Cayley graphs over a cyclic group of odd prime power order,and then investigates the generalized Cayley graphs over a cyclic group of 2n(n≥2).In Chapter 4,we deal with the generalized Cayley graphs of valency 3,4 on the cyclic group G of order 4a(a is an odd integer).In Chapter 5,we classify the generalized Cayley graphs of valency 5 on the cyclic group G of order 4a(a is an odd integer)which are vertex-transitive but not Cayley graphs.