论文部分内容阅读
判断一个图是否为哈密尔顿图是结构图论中的一个重要的NP-完全问题,至今没有一个完美的刻画,因此一直受到图论及数学工作者的关注。近年来,借助于图的矩阵表示谱,给出哈密尔顿图的谱充分条件,己成为研究哈密尔顿问题的新方法,并产生了诸多新结果。 本文主要研究给定大的最小度的图的哈密尔顿性的谱刻画。首先研究利用给定大的最小度条件的图的谱半径或补图的谱半径刻画图的哈密尔顿-连通性和从每一点出发都可迹的。其次利用给定大的最小度条件的图的补图的谱半径刻画图是s-连通,s-边-连通,s-路-覆盖,s-哈密尔顿和s-边-哈密尔顿的。然后利用给定大的最小度条件的平衡二部图的谱半径刻画图的可迹性和哈密尔顿性。最后利用给定大的最小度条件的拟平衡二部图或拟补图的谱半径刻画图的可迹性.主要内容安排如下: 第一章,首先介绍本文的研究背景与意义,然后介绍本文所涉及的术语和概念,最后介绍本文研究问题的进展以及主要结论; 第二章,讨论一般图的哈密尔顿性的谱刻画; 第三章,讨论平衡二部图的哈密尔顿性的谱刻画; 第四章,讨论拟平衡二部图的可迹性的谱刻画。