具有两个单特征值的循环图

Cyclic Graphs with Two Simple Eigenvalues

一个图的特征值通常指的是它的邻接矩阵的特征值,图的谱指的是其特征值和特征值的重数.在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的好的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特征值.给出恰好具有两个单特征值的循环图,说明了Petersdorf和Sachs给出的取值范围内部分值的可达性.

The eigenvalues of a graph are usually referred to the eigenvalues of its adjacent matrix.The spectrum of a graph is the set of its eigenvalues together with their multiplicities.Among all the eigenvalues,the simple eigenvalues(eigenvalues with multiplicity 1)are especially important.To make sure of the simple eigenvalues of a graph is quite difficult because of no general methods.In 1969,Petersdorf and Sachs gave the possible simple eigenvalues of a vertex-transitive graph.But,to find out which is indeed simple among the possibilities still depends on the graph itself.In this paper,we give cyclic graphs with two simple eigenvalues.In some sense,this partly proves the reachability of the values given by Petersdorf and Sachs.