论文部分内容阅读
简单图的Laplace矩阵,在二十世纪七十年代初引起了研究者的注意,并逐渐成为代数图论的热点,取得了很多优美的结论,特别是用其特征值来估计图的诸多不变量。近年来,图的Laplace矩阵研究工作转到混合图或者符号图上,试图把简单图的若干结论推广到混合图上,特别是通过混合图的Laplace谱给出图的结构或不变量的更好刻画。
针对混合图,本文主要研究两方面的内容:(1)特征值与顶点度的关系;(2)混合图谱半径达到极大的图。
记d<,1>(G),d<,2>(G)分别为图G的最大和次大度;λ<,1>(G),λ<,2>(G)分别为图G的Laplace矩阵的最大和次大特征值.设G为至少有3个顶点和一条边的连通简单图. Grone和Merris证明了:(i)λ<,1>(G)≥d<,1>(G)+1;Li和Pan证明了: (ii)λ<,2>(G)≥d<,2>(G).Zhang和Luo证明了(i)对混合图也成立,那么(ii)对混合图也成立吗?我们对该问题展开研究,给出了,(ii)成立的一个充分条件。
Fan分别刻画了Laplace谱半径达到最大和最小的单圈混合图,并进一步给出了Laplace谱半径达到次大和第三大的单圈混合图;Fan,Tam和作者本人刻画了Laplace谱半径达到最大的双圈混合图。一个很自然的问题就是如何刻画Laplace谱半径达到最大的多圈混合图?我们用简洁的方法,统一处理了圈空间维数小于4的多圈混合图。
本文共由三章组成.第一章给出本文所必需的预备知识及研究背景。第二章研究了混合图的Laplace矩阵的第二大特征值λ<,2>(G)和次大度d<,2>(G)的关系,获得了λ<,2>(G)≥d<,2>(G)的一个充分条件。在具有相同点数和边数的混合图中,如果一个图的Laplace谱半径达到最大,则称该图为极大图.在第三章,我们统一刻画了圈空间维数小于4的极大图。