二部图的单特征值

Simple Eigenvalues of Bipartite Graphs

一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特征值.给出一类正则二部图,它们是二面体群的凯莱图,这类图的单特征值中除了它的正、负度数之外还有0或者±1,而它们恰好是Petersdorf和Sachs所给出的单特征值范围内的中间取值.

The eigenvalues of a graph are usually referred to the eigenvalues of its adjacent matrix.Among all the eigenvalues,the simple eigenvalues(eigenvalues with multiplicity 1)are especially important.In lack of no general methods,it is quite difficult to determine the simple eigenvalues of a graph.In 1969,Petersdorf and Sachs gave a scope of the possible simple eigenvalues of a vertex-transitive graph.But,to find out which one is indeed simple among the possible values still depends on the graph itself.In this paper,we give a class of bipartite graphs which are also Cayley graphs of dihedral groups.Apart from the degrees and minus degrees of these graphs,the other simple eigenvalues are 0 or ±1 that are exactly the "median" values in the scope given by Petersdorf and Sachs.