导　　师： 许宝刚

学科专业： G0101

授予学位： 博士

作　　者： ;

机构地区： 南京师范大学

摘　　要： 令ρ(G)、A(G)和μ(G)分别表示图G的谱半径、拉普拉斯谱半径和无符号拉普拉斯谱半径.令J(π)表示以π为度序列的简单连通图的集合.设π=(d1,d2,...,dn)和π’=(d’1,d’2,...,d’n)分别为两个连通图的度序列.我们用符号π<π’来表示π和π’满足以下关系：π≠π’,∑ni=1di=∑ni=1d’i,且对于任意的j∈{1,2,...,n}都有∑ji=1di≤∑ji=1d’i.这种关系π(?)π’常常被称为优超[30].由于很多拓扑指数与图谱有密切联系(例如,Kirchhoff指数被证明可被图的拉普拉斯谱来表示[100],而Wiener指数以及hyper-Wiener指数也与图的拉普拉斯特征多项式的系数有密切联系[27]),并且图谱与拓扑指数的研究技巧可以相互渗透[43,59],因此在本文中我们将关注于图谱以及与其密切相关的一些拓扑指数的研究.1981年,图谱专家Cvetkovic [8]指出了图谱理论中进一步研究的十二个方向,其中之一就是“依图的谱对图进行分类和排序”.此后各图类依图谱,特别是依谱半径或(无符号)拉普拉斯谱半径的排序问题被大量研究.我们的研究结果大致可以分为两类：一类是关于特殊图类依图谱或拓扑指数排序的研究,另一类是和Cvetkovic排序问题密切相关的图谱理论中的极值问题.具体工作如下：1.2008年,Biyikoglu和Zhang等人分别确定了给定度序列的树中谱半径和无符号拉普拉斯谱半径的唯一极大图,此后给定度序列的连通图中的极图问题受到越来越多的关注.至今为止,学者们已经确定了给定度序列的树、单圈图、双圈图的(无符号拉普拉斯)谱半径的唯一极大图,也确定了给定度序列的树中具有极大Wiener指数的唯一极图以及具有极大的子树数目的唯一极图,并且还确定了对于任意的正整数k,在给定度序列的树中具有极大的距离不超过k的点对数目的唯一极图.本文中,我们得到了给定度序列的连通图中(无符号拉普拉斯)谱半径的极大图的一些性质,我们也对在给定度序列的简单连通图中(无符号拉普拉斯)谱半径的极大图进行了更精细的刻画,改进了[Biyikoglu, Leydold, Electron. J. Combin.15(1)(2008)]和[Zhang, Discrete Math.308(2008)]的相应结果,同时我们还确定了给定度序列的三圈图中(无符号拉普拉斯)谱半径的极大图,给出了Belardo关于极图“结构唯一性”猜想的反例.在拓扑指数方面我们确定了给定度序列的树中具有极大的Wiener弹性指数的一个极图,并且也确定了给定度序列的树以及单圈图中具有极大第二类Zagreb指数的一个极图.2. Biyikoglu等人在2008年证明了以下的有趣结论：如果π和π’是两个树的非增的度序列并且π(?)π’,而T和T’分别是J(π)和J(π’)中谱半径的极大图,则ρ(T)<ρ(T’).后来,Liu等人把这种关系称为“优超定理”.至今为止,在图谱理论方面,学者们证明了树、单圈图和双圈图的(无符号拉普拉斯)谱半径的优超定理.而在拓扑指数方面,学者们证明了树的Wiener指数、树的距离小于等于k的点对数目、树的子树数目的优超定理,我们也证明了在任意简单连通图中第一类(广义)Zagreb指数的优超定理,而Eliasi证明了在任意简单连通图中第一类和第二类多重Zagreb指数的优超定理.本文中,在图谱理论方面我们通过例子说明并非任意的简单图的谱半径或者(无符号)拉普拉斯谱半径之间都存在相应的优超定理,我们证明了两个标准优超关系的度序列之间存在优超定理,并且一般连通图的度序列之间也存在优超定理,推广了[Biyikoglu, Leydold, Electron. J. Combin.15(1)(2008)]和[Zhang, Discrete Math.308(2008)]的相应结果,我们还证明了某些特殊的度序列之间也有相应的优超定理.而在拓扑指数方面我们证明了树和单圈图的第二类Zagreb指数、树和单圈图的第二类Zagreb补指数、以及任意简单连通图中第一类Zagreb补指数的优超定理.3.令△(G)表示图G的最大度,且令C(n,Δ；c)表示最大度为△的n阶c圈图的图类.符号f(n,Δ,c,p)表示当△(G)≥f(n,Δ,c,ρ)且△(G)>△(G’)时p(G)>p(G’)的一个数值,f(n,Δ,c,λ)表示当Δ(G)≥f(n,Δ,c,λ)且△(G)>Δ(G’)时λ(G)>λ(G’)的一个数值.2006年,Lin等人确定了△≥[n/2]时C(n,△；0)中唯一的谱半径极大图,并证明了f(n,Δ,0,,ρ)≥[2n/3]—1.后来,Yuan等人确定了△≥n/2+1时C(n,Δ；1)中唯一的谱半径极大图以及△≥n+3/2时C(n,Δ；2)中唯一的谱半径极大图,并且证明了f(n,△,1,p)≥[7n/9]+1和f(n,Δ,2,ρ)≥[7n/9]+9.2009年,Yuan等人开始考虑树的拉普拉斯谱半径的类似问题.她们首先确定了△≥n/2时C(n,Δ；0)中唯一的拉普拉斯谱半径极大图,并且证明了f(m,△,0,λ)≥[n/2]+1.2011年,Yuan等人把界“[n/2]+1”改进为“[11n/30]+1”并通过具体例子说明界“[11n/30]+1”是最优的.本文中,我们确定了c≥0,n≥3c且△≥n+2c+1时C(n,Δ；c)的(无符号拉普拉斯)谱半径的极大图结构,推广了[Lin,Guo,Linear Algebra Appl.418(2006)],[Yuan,Chen,Discrete Math.310(2010)],[Yuan,Shan,Wu,Ars Combin. CII(2011)],[Yuan,Shan,Liu,Discrete Math.309(2009)]等论文的相应结果；我们还确定了△≥n/2+2时C(n,Δ；3)中唯一的谱半径极大图,n+1/2≤△≤n-3时C(n,Δ；0)中唯一的极大以及次大的极图,n/2+1≤Δ≤n-3时c(n,△；1)中唯一的极大以及次大的极图,n+3/2≤△≤n—2时C(n,△；2)中唯一的极大以及次大的极图；并且我们还证明了f(b,Δ,1,ρ)≥1/9(1+6n+10)2,f(n,Δ,2,.ρ)≥1/9(2+6n+28)2和f(n,△,3,ρ)≥(1+6+2n/3)2,改进了[Yuan,Chen,Dis-crete Math.310(2010)]和[Yuan,Shan,Wn,Ars COMBIN.CII(2011)]的相应结果.同时,我们证明了“设G和G’是两个有m条边的n阶简单连通图.若△(G)≥m—n-3/且△(G)>△(G’),则A(G)>λ(G’)且μ(G)>μ(G’)”,并通过具体例子说明我们所得到的界“m—n-3/2”对于无符号拉普拉斯谱半径而言是最优的.4.称一个具有m条边的n阶简单连通图为一个(m,n)图.至今为止,研究(m,n)图类中极大谱半径或(无符号)拉普拉斯谱半径的Cvetkovic排序问题的结果已经有很多,相关的研究文献不少于三十篇,但已有的方法都具有特殊性而不能进行一般化.2006年,Lin等人得到了一种用来解决树的极大谱半径排序问题的有效方法,后来Yuan等人证明了这种方法还可以解决单圈图和双圈图的极大谱半径以及树的极大拉普拉斯谱半径的排序问题.本文中,我们证明了优超定理也是一种解决(m,n)图类中Cvetkovic排序问题的有效方法,并且证明了Lin型方法还可以解决m≤3n-5/2时(m,n)图的极大(无符号)拉普拉斯谱半径以及三圈图的极大谱半径的排序问题.优超定理以及Lin型排序方法的基本想法都是把(m,n)图类中极大谱半径或(无符号)拉普拉斯谱半径的排序问题转化为对那些具有较大最大度的图的谱半径或(无符号)拉普拉斯谱半径进行排序.利用这两种方法我们可以非常容易地推导出该领域中所有的已知排序结果,并且还可以轻易地把现有的排序进行改进.5.设c≥0,k≥1,令L(n,c,k)表示恰有k个悬挂点的n阶c圈图的图类.Wu等人最先在2005年确定了L(n,0,k)中谱半径的极大图,此后L(n,c,k)中(无符号)拉普拉斯谱半径和谱半径的极大图问题受到了广泛的关注.至今为止,学者们已经确定了L(n,0,k),L(n,1,k),L(n,2,k)和L(n,3,k)中(无符号)拉普拉斯谱半径的极大图以及谱半径的极大图.本文中,我们确定了当n≥2c+k+1时L(n,c,k)中无符号拉普拉斯谱半径的极大图,并且还确定了对于任意的n,L(n,c,k)中拉普拉斯谱半径的极大图,推广了关于L(n,c,k)中(无符号)拉普拉斯谱半径的极大图的所有已知结果.

关 键 词： 度序列 优超定理 最大度 悬挂点 向量

分 类 号： [ZZ]