The Extendability And Spectrum Of Semi-Cayley Graphs

A connected graphΓis called k-extendable if|V(Γ)|≥2k+2 and every matching of size k inΓcan be extended to a perfect matching ofΓ. The spectrum of a graphΓis the set of numbers which are eigenvalues of A(Γ), together with their multiplicities.Yu et al characterized the 1-extendability and 2-extendability of Cayley graphs over abelian groups and posed two open questions:(1) Characterize 3-extendable abelian Cayley graphs and, in general, k-extendable abelian Cayley Graphs; (2) Characterize 1-extendable and 2-extendable Cayley graphs. Semi-Cayley graphs are generalization of Cayley graphs. In this thesis, we mainly study the extendability of Semi-Cayley graphs over groups. As applications, we characterize the 2-extendability of a Cayley graph over a non-abelian group. In addition, we give a formula of the spectrum of semi-Cayley graphs over finite abelian groups. This thesis consists of five chapters.In Chapter 1, we first introduce some basic concepts, terminology and notations. Then we point out the research backgrounds. Finally, we survey the research developments in this area and make a brief introduction to the main results obtained in the thesis.Bi-Cayley graphs are special Semi-Cayley graphs. In Chapter 2, we explore the extendability of Bi-Cayley graphs over finite abelian groups. In particular, we character the 2-extendable and 3-extendable Bi-Cayley graphs over finite abelian groups, respectively.In Chapter 3, we study the extendability of Bi-Cayley grpahs over finite non-abelian groups. In particular, we characterize the 1-extendability of Bi-Cayley graphs over finite groups and the 2-extendability of Bi-Cayley graphs over dihedral groups.In Chapter 4, we classify the 1-extendable and 2-extendable Semi-Cayley graphs SC(Dn; R, R,T) over dihedral groups, respectively. As an application, we characterize the 2-extendable Cayley graph over the group Dn x Z2.In Chapter 5, we give a formula of the spectrum of Semi-Cayley graphs over finite abelian groups. In particular, we give the spectrum of Cayley graphs over dihedral groups and dicyclic groups, respectively.