【作者】 高兴；

【导师】 罗彦锋；

【作者基本信息】 兰州大学 ， 基础数学， 2010， 博士

【摘要】 连通图r称为κ-可扩的,如果|V(Γ)|≥2κ+2,且r的每个大小为κ的匹配均可以扩充为r的一个完美匹配.图r的谱是r的邻接矩阵A(r)的特征值以及它们的重数.于青林等人刻画了有限阿贝尔群上的Cayley图的2-可扩性,且提出了两个公开问题：(1)刻画有限阿贝尔群上的Cayley图的3-可扩性和κ-可扩性；(2)刻画任意群上的Cayley图的1-可扩性和2-可扩性.Semi-Cayley图是Cayley图的自然推广.本文主要研究群上的Semi-Cayley图的匹配可扩性.作为应用,我们刻画了一类非阿贝尔群上的Cayley图的2-可扩性.另外,给出了有限阿贝尔群上的Semi-Cayley图的谱.全文共分为五章.在第一章中,我们首先介绍了本文所需要的基本概念,术语和记号,然后指出本文所研究问题的背景,进而综述了该领域的研究进展和本文所得到的主要结论.Bi-Cayley图是特殊的Semi-Cayley图.在第二章中,我们研究了有限阿贝尔群上的Bi-Cayley图的匹配可扩性.特别地,分别刻画了有限阿贝尔群上的Bi-Cayley图的2-可扩性和3-可扩性.在第三章中,我们研究了有限非阿贝尔群上的Bi-Cayley图的匹配可扩性.特别地,分别刻画了任意有限群上的Bi-Cayley图的1-可扩性和二面体群上的Bi-Cayley图的2-可扩性.第四章我们研究了二面体群Dn上的Semi-Cayley图SC(Dn；R,R,T)的1-可扩性和2-可扩性.作为应用,刻画了群Dn×Z2上的Cayley图的2-可扩性.在第五章中,我们给出了有限阿贝尔群上的Semi-Cayley图的谱公式,证明了二面体群和双循环群上的Cayley图是有限阿贝尔群上的Semi-Cayley图,从而给出了二面体群和双循环群上的Cayley图的谱公式.更多还原

【Abstract】 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.更多还原