特征值互不相同的图

作     者：马志辉 

作者单位：新疆大学 

学位级别：硕士

导师姓名：黄琼湘

授予年度：2011年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：特征值 特征多项式 特征向量 直径 

摘      要：图的特征值是图论与代数的一个交叉研究领域,是代数图论的一个分支.在1974年, F. Harary和A. J. Schwenk在文献[1]中提出了一个开放问题:哪些图的特征值互不相同?但不幸的是到目前为止这方面的结论很少.本文主要用特征多项式和交错定理刻画直径为d(G) = n - 2特征值互不相同的图,主要内容如下: 在第一章引言中,我们给出了特征值的有关定义,符号及记号,并且回顾了特征值的研究历史及现状.列举了前人的一些关于k个互不相同特征值的研究成果. 第二章分为三节,第一节介绍了一些本文中证明所需要的一些重要引理,推论.第二节给出了直径为d(G) = n - 2图的结构并根据图的奇偶性把图G (见图2)分为两类:前两种类型记作: D = {P,P| 1≤k≤n - 3},而后两种类型记作:D = {P(1≤k≤n - 2),P(1≤k≤n -3}.第三节完全刻画了在D中特征值互不相同的图. 第三章我们首先介绍了交错定理,并运用交错定理和矩阵的特征向量部分刻画了在D中特征值互不相同的图.设图G是一个具有n个顶点,直径为d(G) = n-2的非二部图(如图4(a),(b)所示),其中n≥4.如果3(?)n ,则图G有n个互不相同的特征值.