Symmetry Of Bi-cayley Graphs

The symmetry of graphs is a hot topic in algebraic graph theory.A graph ? is said to be vertex-transitive,edge-transitive and arc-transitive if its full automorphism group acts transitively on its vertex set,edge set and arc set,respectively.A graph? is said to be half-arc-transitive if it is both vertex-transitive and edge-transitive but not arc-transitive.A half-arc-transitive graph is said to be half-arc-regular if its full automorphism group acts regularly on its edges.A graph is said to be a Cayley graph over a group H if it admits H as a regular automorphism group.A graph is said to be a bi-Cayley graph over a group H if it admits H as a semiregular automorphism group with two vertex-orbits.This thesis investigates the symmetry of bi-Cayley graphs and g-extra connectivity of folded hypercubes.This thesis is organized as follows.In Chapter 1,we introduce some basic definitions regarding finite group theory and graph theory,and the relative background of our main work on the symmetry and g-extra connectivity of graphs.In Chapter 2,we investigate connected trivalent bi-dihedrants.A bi-dihedrant is a bi-Cayley graph over a dihedral group.In this chapter,we give a classification of connected trivalent edge-transitive or vertex-transitive non-Cayley bi-dihedrants.In Chapter 3,we focus on two classes of half-arc-transitive bi-Cayley graphs,that is,bi-Cayley graphs over abelian and non-abelian metacyclic p-groups.For bi-Cayley graphs over abelian groups,it is shown that 6 is the smallest possible valency of half-arc-transitive bi-Cayley graphs over abelian group.As an application,we prove that no hexavalent half-arc-transitive graphs of order twice a prime square exist.Besides,a classification is given of connected half-arc-regular bi-Cayley graphs over cyclic groups of valency 6.For bi-Cayley garphs over non-abelian metacyclic p-groups with an odd prime p,a complete classification is given of connected tetravalent half-arc-transitive bi-Cayley graphs over metacyclic p-groups.As an application,a complete classification of con-nected tetravalent half-arc-transitive graphs of order twice a prime cube is given.In Chapter 4,we first prove that every Bouwer graph is a Cayley graph,and then determine the full automorphism groups of Bouwer graphs.In Chapter 5,we investigate the g-extra connectivity of folded hypercube FQn.Given a connected graph ? and a non-negative integer g,the g-extra connectivity of ? is the minimum cardinality of a set of vertices in ?,if it exists,whose deletion disconnects? and leaves each remaining component with at least g + 1 vertices.In this chapter,we determine the g-extra connectivity of FQn for all 0 ? g ? n + 1 and n?7.In Chapter 6,we propose some open problems for our future research.