论文部分内容阅读
代数图论是图论研究的一个重要领域,它广泛的应用于生命科学,计算机网络,组合优化,生物化学,分子理论等学科中.图的谱刻画理论是代数图论的一个重要的研究方向,它用矩阵论、组合设计、群论等知识来研究图与图矩阵的特征多项式、特征值以及特征向量有关的各种代数参数、组合参数,从而得到谱与图的结构性质之间的关系.因此,利用图的谱来确定图,即图的谱确定问题是图的谱刻画理论中的一个主要课题.所以刻画具有较少的正特征值(小正惯性指数)的图类是一个重要的,有趣的问题.早在1977年,Smith[44]就证明了恰有1个正特征值的图类是完全多部图与一些孤立顶点的不交并,这一结论广泛的应用于图谱理论的研究中.但到目前为止,恰有2个正特征值的图类只在一些特殊的情况得到了刻画.本文将完整的给出恰有2个正特征值的图类的刻画.全文可以划分为6个章节,下面给出各个章节的内容简介:第1章是绪论部分,首先阐述了图的谱刻画方面的研究背景,然后介绍了本文所用到的一些基本的概念和表示符号,最后简介了与本文内容相关的问题的研究进展,及本文的主要结果.第2章具体给出了Ⅰ-,Ⅱ-,Ⅲ-型和Ⅳ-型四种图的合同变换的定义,并通过矩阵的合同变换性质给出这四种图的合同变换的一些简单的性质.特别说明一下,这里的Ⅰ-,Ⅱ-型和Ⅳ-型图的合同变换在其他一些文章中也提及过,但是Ⅲ-型的图的合同变换是我们独创的定义.用Tn0表示恰有2个正特征值,没有零特征值的n阶图的集合.第3章介绍了Oboudi[37]给出一些有用的定义,并详细的回顾了 Oboudi刻画的图集Tn0.事实上,图集Tn0是由48个无限族图(见表6.1)和601个特定图组成的,在本文的第4章中我们将详细的列出这些无限族图.用Tn1真表示恰有2个正特征值,1个零特征值的n阶图的集合.第4章完整的刻画了图集Tn1.具体的来说,利用Ⅰ-,Ⅱ-,Ⅲ-型和Ⅳ-型四种图的合同变换和图集Tn0中的图,可以构造出完全确定的四个图集Tn0(Ⅰ),Tn1(Ⅱ),Tn1(Ⅲ)和Tn1(Ⅳ).我们首先证明了Tn1中的非连通图属于图集Tn1(Ⅰ)或Tn1(Ⅳ).接下来选取图集Tn1中的连通图的一个特殊的导出子图,通过这个导出子图的结构可以将图集Tn1中的图分为三类进行讨论.证明了图集Tn1中的连通图除了有限个以外,其余的都在图集Tn1(Ⅰ),Tn1(Ⅱ)和Tn1(Ⅲ)中.事实上,图集Tn1是由图集Tn1(Ⅰ),Tn1(Ⅱ),Tn1(Ⅲ)和Tn1(Ⅳ)中的图和802个特定图(见表6.1)组成的.用Tns表示恰有2个正特征值,s(2 ≤s ≤n-3)个零特征值的n阶图的集合.第5章进一步完整的刻画了图集Tns.和第四章类似,利用Ⅰ-,Ⅱ-,Ⅲ-型和Ⅳ-型四种图的合同变换和图集Tn1中的图,可以递推的构造出完全确定的图集Tns(Ⅰ),Tns(Ⅱ),Tns(Ⅲ)和Tns(Ⅳ).因为图集Tns中的图与Tn1中的图的结构类似,所以我们采用了与第4章类似的方法进行讨论.事实上,图集Tns是由图集Tns(Ⅰ),Tns(Ⅱ),Tns(Ⅲ)和Tns(Ⅳ)中的图和175个特定图(见表6.1)组成的.因为本文研究工作中的概念、符号较多,第6章将对前面的证明过程和方法做一个总结.用Tn表示恰有2个正特征值的n阶图的集合,则Tn=Us=0n-3Tn0.为了将图集Tn中的图做一个分类,我们定义了可构造图和不可构造图.实际上,图集Tn0(Ⅰ),Tn0(Ⅱ),Tn0(Ⅲ)和Ts(Ⅳ)(1 ≤s≤n-3)中的图都是可构造的,而图集Tns中的图、图集Tn1中的802个特定图以及图集Tn2中的175个特定图都是不可构造的.因此图集Tn是可构造图和不可构造图的不交并.另外,我们给出一个例子来说明图集Tn中的图的构造方法.最后提及到了利用本文的结果可以开展的一些研究工作展望.