两类图的谱确定问题研究

来源 :新疆大学 | 被引量 : 0次 | 上传用户:jendychan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图谱理论起源于理论化学家和物理学家为解决一类偏微分方程的数值解而建立起来的一套离散的图模型.它在物理学、化学、计算机科学及通信网络等方面都有着十分广泛的应用.图谱理论主要是利用矩阵理论中的方法和技巧,来研究图矩阵(如邻接矩阵A,拉普拉斯矩阵L=D-A,无符号拉普拉斯矩阵Q=D+A,规范拉普拉斯矩阵?L=D-12 LD-12,Seidel矩阵S=J-2A-I等)的谱(特征值及其重数)的性质进而用这些性质来反映图的一些结构性质和拓扑性质,它是代数图论中一个重要的研究领域.图谱理论研究的内容相当广泛,概括起来主要包括两个方面,一个方面是图的谱特征,主要涉及确定图的谱及其分布,确定谱的性质,谱与图的各种参数(例如直径,色数,围长,连通度等)之间的关系等;另一个方面是谱的图特征,主要是根据谱的性质刻画图等,其中图的谱确定问题是其研究的重点.两个图同谱是指它们有相同的谱.两个图同谱不一定同构,但是两个图同构则一定同谱.一个图G被称作是由谱确定的,如果对于任意一个图H,由H与G同谱蕴含着H与G同构.图的谱确定问题是指,对于一个图,首先考虑该图是否由谱确定;其次如果该图不能由谱确定则考虑找出它所有的同谱图.图的谱确定问题最早由G¨unthard和Primas提出,接着van Dam和Haemers发表了两篇综述文章对此问题进行了概括总结,并给出了很多谱确定图及图同谱的必要条件.但是“哪些图是由它的谱所确定的”这个问题还远远没有解决.从已经取得的研究结果来看,谱确定问题主要考虑具有一定特性的图,如对称性较好的图、谱半径在一定范围之内的图、特征值个数较少的图、非正则且度序列中不同度数较少的图(例如几乎正则图)等.虽然目前已经知道了很多谱确定图,但是要考虑一般图是否由谱所确定还是有很大难度的.在本文中,我们主要考虑两类图的谱确定问题,一类是第二大特征值小于等于1的单圈图的邻接谱确定问题,另一类是4-玫瑰图的拉普拉斯谱确定及无符号拉普拉斯谱确定问题.本文结构安排如下:第一章首先简要介绍了图谱理论的研究背景及应用.其次给出了本文要用到的基本概念和符号.随后对谱确定问题的来源,国内外研究现状及发展动态做了概括总结.此外,我们还引入了一些研究谱确定问题常用的工具、方法及结论.最后介绍了本文的主要研究工作.对第二大特征值不超过1的图的刻画已经取得了很多研究成果,本论文的第二章则从图的谱确定角度来研究这些图.我们主要考虑第二大特征值小于等于1的单圈图的邻接谱确定问题.首先我们对第二大特征值小于等于1的所有单圈图进行分类并且证明了具有这一性质的所有单圈图之间不是邻接同谱的.其次我们给出了与具有这一性质的图邻接同谱的必要条件并且找到了一些禁止子图.再次,我们根据分类逐一考虑了这些图的谱确定性.其中重点证明了图Gt,s是由它的邻接谱所确定的.最后,利用禁止子图条件证明了在第二大特征值小于等于1的单圈图中,除了四个图外,其它的图都是由它们的邻接谱所确定的.此外,我们还给出了不能由邻接谱所确定的那些图的同谱对.具有p个花瓣的图(简称为p-玫瑰图)是指p个圈恰有一个公共顶点的图,“玫瑰图”的得名由玫瑰曲线而来.玫瑰图的谱确定问题一直受到人们的关注.第三章我们考虑了4-玫瑰图的拉普拉斯谱确定性.首先我们介绍了两个图L-同谱的一个必要条件.其次根据4-玫瑰图的组合结构给出了它的拉普拉斯特征多项式中倒数第三项的系数.另外,我们还给出了4-玫瑰图的拉普拉斯特征多项式的表达式.最后根据4-玫瑰图的拉普拉斯谱半径的界得出L-同谱于4-玫瑰图的图可能的度序列.最终证明了4-玫瑰图是由它的拉普拉斯谱所确定的.第四章我们讨论了4-玫瑰图的无符号拉普拉斯谱确定性.我们首先引进了一个新的Q-同谱不变量并给出了4-玫瑰图的无符号拉普拉斯特征多项式的表达式.其次介绍了Q-同谱于4-玫瑰图的图可能的形.再次,利用无符号拉普拉斯谱半径的界讨论了Q-同谱于4-玫瑰图的图可能的度序列.最后利用Q-同谱图的新的不变量和图中三角形的数目证明了4-玫瑰图是由它的无符号拉普拉斯谱所确定的.
其他文献
随着我国军事力量不断发展,军种、战区等不断改革,加之中国特色社会主义法治社会越趋完善,依法治军思想的深入,对军事法领域的探究就更为重要,而对于军事法是否应成为独立的
<正>《义务教育品德与社会课程标准(2011年版)》中明确指出,"充分开发、有效利用课程资源,对于丰富品德与社会课程内容,增强课程的开放性、生成性和教学活力具有重要的意义".
碳化硅(SiC)材料由于其优良的高温力学性能、高温化学惰性、低感生放射性和强抗腐蚀能力,尤其是其低中子俘获截面等特性,使之成为先进核能系统熔盐堆的候选材料之一,可作为结
罗马法和日耳曼法均被认为是法律形式主义传统的源头和代表。究其原因,很大部分是因为西方这两大古代法律秩序都崇尚形式,很多时候将规范的效力与形式挂钩。而形式的意涵在历
强夯技术已经在土木工程建设领域中得到广泛的应用和推广,在高速公路建设过程中,强夯法主要应用在处理各类碎石土、砂性土、湿陷性黄土、低饱和度的粉土、回填土及垃圾土等特
最近几年电瓶车火灾频发,造成了人员、财产巨大损失。在对具有典型代表的电瓶车火灾事故进行调查分析,了解电瓶车火灾发生的特点,并从生产厂家、使用消费者和政府监管部门,多
通过对北京海淀区中学领导干部听课评课记录的分析,发现领导干部听课评课尚不专业,表现为:听课评课目的不明确,计划性、选择性不强,框架不清晰,对学生的学习效果关注不够,听
由家族成员与非家族成员轮流执掌135年美国艾欧史密斯公司1874年由查尔斯·史密斯创办。艾·欧·史密斯是子承父业。目前它是北美热水器市场领头羊,在全球建有43家工厂。在13
通过对柴油机燃烧过程的分析,具体介绍了针对4JB1柴油机建立并用于发动机硬件在环实时仿真的燃烧放热模型。出于实时性考虑,采用零维单区燃烧模型,在实时仿真系统中将Wiebe模型
铋基半导体材料在解决环境污染和能源紧缺问题方面具有极大的应用潜力,因此,铋基半导体及其复合物材料的合成及应用一直是光催化材料研究领域的热门课题。随着这一领域不断的