Edge-transitive Bi-Cayley Graphs And Stability Of Graphs

The symmetry and stability of graphs are important topics in algebraic graph theory and has been studied extensively.A graph is said to be a bi-Cayley graph over a group H if it admits H as a group of automorphisms acting semiregularly on its vertices with two orbits.The canonical double cover D(X)of a graph X is the direct product of X and K2.If Aut(D(X))(?)Aut(X)×Z2 then we say that X is stable;otherwise X is unstable.This dissertation focuses on edge-transitive bi-Cayley graphs over metacyclic p-groups with p an odd prime and the stability of circulants and generalized Petersen graphs,which is organized as follows.Chapter 1 briefly introduces the history and background for symmetry and stability of graphs,as well as our main work in this dissertation.Chapter 2 introduces some basic definitions and results regarding finite group the-ory and graph theory.In Chapter 3,a classification of connected cubic edge-transitive bi-Cayley graphs over non-abelian metacyclic p-groups.In Chapter 4,a classification of connected cubic edge-transitive bi-Cayley graphs over inner-abelian p-groups.In Chapter 5,a classification of connected edge-transitive bi-Cayley graphs over non-abelian metacyclic p-groups of valency p.In Chapter 6,we use bi-Cayley graphs to construct three infinite families of con-nected hexavalent semisymmetric graphs.Chapter 7 is devoted to studying the stability of circulants.We prove that every circulant graph of odd prime order is stable.In this chapter we also prove that there is no arc-transitive nontrivially unstable circulant graph,which answers a question of Wilson in 2008.Chapter 8 is devoted to studying the stability of generalized Petersen graphs.We completely determine the full automorphism group of the canonical double cover of generalized Petersen graphs.As a result,we confirm a conjecture of Wilson in 2008 which is about the stability of generalized Petersen graphs.In Chapter 9,we summarize the main conclusions of this dissertation and propose some open problems for further research.