论文部分内容阅读
谱图理论是代数图论的一个重要研究领域,主要研究图的各种代数表示(如Laplace矩阵,邻接矩阵和无符号Lapace矩阵)的谱性质,并用谱性质来刻画其拓扑结构性质.众所周知,所有Hamilton图必然是2点(边)-连通的,并且图的连通度越大,则其为Hamilton图的可能性越大.故,图的Hamilton性与连通性有着密切的关系.本文应用谱来研究这两类相关问题,即图的Hamilton性与连通性.具体内容如下：早期Hamilton图的充分条件都蕴涵着图的边很多,或者说图是稠密的.例如,1952年Dirac给出的最小度条件,1960年Ore给出的不相邻点的度和条件,1972年Chvatal和Erdos利用连通度与独立数关系给出的充分条件.但当图的顶点较多时,上述条件或类似的充分条件,很难直接判定图的Hamilton性.2010年Fiedler和Nikiforov利用图的邻接矩阵谱半径给出Hamilton图的充分条件.随后周波应用图的无符号Laplace谱半径来刻画图的Hamilton性.这些判别条件发挥了图谱的易于计算的优点,更便于判断图的Hamliton性.受此启发,本文进一步研究了图的各种矩阵的特征值与图的Hamilton’性的关系,给出Hamilton图的若干条件,并且把此方法应用于具有更高连通性的图的刻画,如Hamilton连通图.实际上,存在大量稀疏Hamilton图,例如圈.但人们对此情形研究较少,其突破性进展是1975年Komlos和Szemeredi给出如下令人惊奇的结果：几乎所有的随机图都是Hamiltoi1图.随后,2003年Krivelevich和Sudakov应用邻接矩阵的谱给出正则图的Hamilton性判别,满足判别条件的图是伪随机的.他们猜测该方法也适用于几乎正则图的Hamilton性讨论.2010年Butler和Chung证实了他们的猜测是可行的,并利用图的Laplace谱给出几乎正则图的Hamilton性的充分条件.2011年Radcliffe提出是否可以利用图的规范Laplace谱给出Hamilton图的充分条件.本文对此问题展开研究,给出了Hamilton图的规范Laplace谱判断,所得结果在正则图的情形下可以推出上述两个工作的结论.由于图的高连通性蕴含着高Hamilton性,所以对图的连通性讨论也极为重要.对于点(边)-连通度为2,3的图,其结构已有很好的刻画.关于代数角度的连通性刻画,最重要的经典概念莫过于Fiedler于1972年提出的图的代数连通度,即图的Laplace矩阵的次小特征值.利用图的邻接矩阵的谱半径,也可给出图的连通度的刻画.但图的邻接矩阵的最小特征值和连通度关系的研究较少.1985年Constantine给出具有极小的最小特征值的极图,即为几乎等部的完全二部图.但这个图的补图是不连通的.因此,本文研究具有连通补图的图的最小特征值,刻画了该类图中最小特征值达到极小的图.另外,考察已有的关于给定补图性质的极小图,它们的补图均含有割点或割边.这就驱动我们讨论补图无割点或割边的图的最小特征值,即补图为2-点(边)连通的图的最小特征值,并刻画此类图中最小特征值达到极小的图.本文最后研究的问题就是探讨图的连通性与图的无符号Laplace最小特征值之间的关系.2008年Cardoso等人给出了非二部图中无符号Laplace最小特征值达到极小的图,其点或边连通度很小.我们猜测,在某个图类中,图的无符号Laplace矩阵最小特征值达到极小的图势必具有很小的连通度.我们对双圈图展开讨论,试图核实我们的想法.研究发现,极小图是小连通度和大二部度之间的一个平衡,即具有尽可能多的割点数与割边数同时具有尽可能多的偶圈.