论文部分内容阅读
本论文主要研究图中结构以及拓扑参数,主要内容如下：在第一章中,我们首先给出了本文相关问题的一些基本概念和符号.接着介绍了本文的研究背景和研究意义,国内外在这方面具有代表性的研究情况.通过对本文研究背景及研究现状的讨论,充分说明了本文的主要研究工作的必要性和创新性.在接下来的四章中,我们将分别对图中结构以及图的几个重要的拓扑参数展开研究.扫帚是将一个星图K1,。的一条边剖分多次后所得到的树,它只含有一个分枝点.在文献[G. Chen, M. Ferrara, Z. Hu, M. Jacobson and H. Liu, Degree conditions for spanning brooms, submitted.]中,Chen等人对此类图的存在性问题提出了以下猜想：设G是阶数为n(n≥3)的连通图.若σ3(G)≥n-2,则G中含有一个支撑扫帚.在第二章中,我们证明了当G的阶数足够大时,此猜想成立,从而基本解决了Flandrin等人在2008年提出的一个公开问题.不仅如此,我们还进一步证明了：若图G是阶数为n的2-连通图,并且σ3(G)≥n-2,则G中存在哈密尔顿路或支撑水母.设图G是阶数为n的连通图.若G的边数为n+1,则称G为双圈图.He,Shao以及He在文献[C. He, J. Shao, J. He, On the Laplacian spectral radius of bicyclic graphs, Discrete Math.308(2008)5981-5995]中确定了n阶双圈图中前四大的Laplacian谱半径并刻画出了所有达到相应谱半径的图.在第三章中,我们将继续对n阶双圈图的Laplacian谱半径从第五大到第八大进行排序,并刻画出所有达到相应谱半径的图.设图G是阶数为n的图.矩阵Q(G)=(In+L(G))-1=(ωij)被称为图G的双随机图矩阵,其中：In表示n×n的单位矩阵,而L(G)表示图G的Laplacian矩阵.设ω(G)为矩阵Ω(G)中的最小元Zhang和Wu在文献[X.D. Zhang, J.X. Wu, Doubly stochastic matrices of trees, Appl. Math. Lett.18(2005)339-343]中确定了n阶树中ω(T)的上下界,并刻画出了相应的极图.在第四章中,作为此问题的延续,我们将在n阶树中继续对ω(T)进行排序,刻画出前[n-1/2]小的树T1,T2…,T[n-1/2]使得ω(T1)<ω(T2)<…<ω(T[n-1/2])≤ω(T[n-1/2])<ω(T),其中Ti是由路Pn-1=v1v2…vi…vm-1在点vi处粘上一个悬挂点后所构成的图,而T是不同于T1,T2….T[n-1/2]的树.对任意的一个图,它的第一类Zagreb指标M1等于所有的点度的平方和,而第二类Zagreb指标M2等于所有相邻点对度之积的总和.若连通图G中任意两个圈至多只有一个公共顶点,则我们称图G为一个cactus.在第五章中,我们将研究具有k个悬挂点的n阶cactus图中两类Zagreb指标的上下界.此外,我们还确定了n阶cactus图中两类Zagreb指标的上界,以及具有完美匹配的n阶cactus图中两类Zagreb指标的上界.