凯莱图的单特征值

Simple Eigenvalues of Cayley Graphs

图的特征值通常指的是其邻接矩阵的特征值,而图的单特征值(重数为1的特征值)在刻画图的特性方面尤其重要.点传递图的单特征值已经有了明确的范围,但是,对于一个给定的点传递图,尚未找到一个好的方法确定其单特征值.凯莱图是一类重要的点传递图,本文将计算两类凯莱图(循环群和二面体群的凯莱图)的单特征值.给出了这两类凯莱图的特征值是单特征值所需要满足的必要条件,同时讨论了这些条件中哪些是充分条件,并给出例子来说明充分条件的复杂性.

Eigenvalues of a graph are usually referred to the eigenvalues of its adjacent matrix.Wherein simple eigenvalues(eigenvalues of multiplicity one)play an especially important role in view of the properties of a graph.There is a general range of the simple eigenvalues of a vertex-transitive graph.But,no good methods have been found to make sure of the simple eigenvalues even for a given vertex-transitive graph.Cayley graphs provide a large family of vertex-transitive graphs.So,in this paper we will calculate the simple eigenvalues of Cayley graphs corresponding to cyclic groups and dihedral groups.Based on the known general range,we give the necessary conditions a simple eigenvalue should satisfy.Also,we give some simple examples to explain the complexity of why these conditions can not be sufficient.