特征值个数较少的图的谱刻画研究

论文摘要

代数图论是图论学科的重要研究领域之一,主要运用代数方法来解决图论问题.代数图论有三个主要分支,分别为图与线性代数,图与群论,图不变量.其中图与线性代数的研究核心是图的谱理论.图谱理论是通过研究与图相关的矩阵（邻接矩阵,拉普拉斯矩阵,无符号拉普拉斯矩阵,正规拉普拉斯矩阵和距离矩阵等）的谱的性质来研究图的组合性质.图谱理论研究兴起于20世纪50-60年代,近20-30年来得到迅猛的发展,它是图论,组合与代数的一个交叉研究领域,是代数图论的重要研究分支.1957年,L.Collatz和U.Sinogowitz的数学论文”Spektren Endhcher Grafen”被视为图谱理论研究的开端,经过50多年的发展,它在图论,物理,量子化学,计算机科学,互联网技术等许多方面都有广泛的应用.图的谱特征往往可以反映出图的结构特征,而不同特征值输数目较少的图通常具有特殊的结构特征（如高度对称性）与较好的组合性质.目前,对含有三个或四个不同特征值的图的谱刻画已取得许多重要进展.然而,对于给定的k<7,恰有k个不同特征值的图的谱刻画问题还远未解决或未完整解决.基于此,本文研究不同特征值数目较少的图的谱刻画问题,主要包括有一个拉普拉斯特征值重数较大的图的谱刻画和邻接特征值数目较少的道半正则图的谱刻画.本文分为三章,具体结构如下:第一章主要介绍了图谱理论的研究背景,接着引入了本文所用到的符号与概念.随后对问题的研究背景以及研究进展作了概述.最后介绍了本文的主要结果.第二章研究了拉普拉斯特征值重数mL（μ）≥n-4的图的谱刻画.首先刻画了集合GL（n,n-3）中的图,即,有一个拉普拉斯特征值是n-3重的图.该类图具有三个或四个不同的拉普拉斯特征值.通过排除若干禁用子图得出结论,GL（n,n-3）中的图,除了Gn,r外均为余图（cograph）,即不含导出P4的图,从而确定了所有这类图.最终与Mohammadian和Tayfeh-Rezaie的结果（GL（n,n-3）中有四个不同拉普拉斯特征值的图的谱刻画）构成了GL（n,n-3）中图类的完整刻画.其次对集合GL+（n,n-4）中的图,即拉普拉斯谱半径为n-4重的图进行了研究.通过排除所有禁用子图得出结论,拉普拉斯谱半径为n-4重的图均为余图（cograph）,从而给出了GL+（n,n-4）（n≥8）中的图的完整刻画.进一步地,我们给出了GL-（n,n-4）（n≥8）,即次小拉普拉斯特征值为n-4重的图的完整刻画.同时证明了,所刻画的图类都是DLS图（由拉普拉斯谱唯一确定的图）.第三章研究了道半正则图的邻接谱刻画.首先给出了道半正则图的定义,即,设G是一个（V1,V2）-半正则图,对任意l>0,从v∈Vi（i=1或2）出发的l长闭道数与v的选取无关,则称G是道半正则图.一个道半正则图一定是半正则图,但是反之则不然.我们证明了,道半正则图一定具有半正则二等价划分,反之,给出了一个半正则二等价划分图成为道半正则图的充分条件.其次重点刻画了具有四个不同特征值的道半正则非偶图.令GW（t,s）表示具有t个不同特征值,其中s个是单特征值（重数为1）的连通非偶道半正则图集合.令GW（t,s;λ）表示含特征值λ的集合GW（t,s）的子集.先确定了集合GW（3,s）（s≤2）中的图,给出了GW（4,3）中图的完整刻画;之后讨论了GW（4,2）中图的性质,重点刻画了GW（4,2;0）中的图类.最后研究了道半正则偶图的相关性质,就偶图的零度（特征值0的重数）达到最大,最小和次小时,刻画了具有五个不同特征值的道半正则偶图.进一步地,针对零度为其他情况时,讨论了这类偶图的存在性并给出了一个必要条件.

论文目录

文章来源

类型: 博士论文

作者: 殷代君

导师: 黄琼湘

关键词: 特征值个数较少的图,拉普拉斯谱,特征值重数,拉普拉斯谱确定,邻接谱,道半正则图,等价划分,偶图

来源: 新疆大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 新疆大学

分类号: O157.5

总页数: 91

文件大小: 1304K

下载量: 79

相关论文文献

• [1].正则图字典积的任意幂的无符号和正规拉普拉斯谱[J]. 陕西理工大学学报(自然科学版) 2020(02)
• [2].3-边可染的3-正则图（英文）[J]. 数学进展 2020(04)
• [3].一类3-正则图完美对集的计数[J]. 大连理工大学学报 2020(04)
• [4].一类k-正则图的生成树数目与熵[J]. 哈尔滨商业大学学报(自然科学版) 2020(04)
• [5].8阶非同构3正则图的构造[J]. 淮阴工学院学报 2019(01)
• [6].8阶三正则图的分类研究[J]. 武汉船舶职业技术学院学报 2018(01)
• [7].基于正则图的锥图的Q-谱确定性[J]. 华东师范大学学报(自然科学版) 2016(06)
• [8].二正则图的和数[J]. 烟台大学学报(自然科学与工程版) 2016(03)
• [9].极大非正则图的边数（英文）[J]. 数学进展 2016(05)
• [10].具有长圈的3-正则图的分解[J]. 昆明理工大学学报(自然科学版) 2016(05)
• [11].构造交错群上的4度1-正则图[J]. 西南师范大学学报(自然科学版) 2016(10)
• [12].三正则图的连通度与条件着色[J]. 中国科教创新导刊 2011(04)
• [13].非正则图同构的算法改进及分析[J]. 西昌学院学报(自然科学版) 2015(01)
• [14].有限素数度弧正则图[J]. 中国科学:数学 2014(03)
• [15].一类3p~2阶4度1-正则图[J]. 数学的实践与认识 2010(22)
• [16].正则图上的进化动态[J]. 兰州大学学报(自然科学版) 2009(06)
• [17].完全图循环分解成2-正则图[J]. 应用数学学报 2008(06)
• [18].二倍无平方因子阶的3度1-正则图[J]. 中国科学(A辑:数学) 2008(02)
• [19].3-正则图的1-因子与割边数[J]. 兰州大学学报(自然科学版) 2008(S1)
• [20].度为奇数的正则图的上负全控制数[J]. 应用数学学报 2008(05)
• [21].正则图的距离标号数的上界[J]. 泉州师范学院学报 2016(06)
• [22].3-正则图的不共边的完美匹配(英文)[J]. 数学研究 2013(04)
• [23].一类具有最大末块数和割点数的4-正则图[J]. 数学的实践与认识 2013(10)
• [24].4p~n阶素数度弧正则图[J]. 云南大学学报(自然科学版) 2013(04)
• [25].8p阶7度1-正则图[J]. 云南民族大学学报(自然科学版) 2012(06)
• [26].非正则图的最大特征值[J]. 纯粹数学与应用数学 2009(01)
• [27].非正则图的谱半径[J]. 数学物理学报 2009(02)
• [28].平方自由阶的4度弧正则图[J]. 萍乡学院学报 2018(06)
• [29].具有正则图的有限格的一些注记[J]. 汕头大学学报(自然科学版) 2010(02)
• [30].无爪3-正则图的独立数[J]. 数学物理学报 2009(01)

标签：特征值个数较少的图论文;  拉普拉斯谱论文;  特征值重数论文;  拉普拉斯谱确定论文;  邻接谱论文;  道半正则图论文;  等价划分论文;  偶图论文;