图的积和谱刻画问题研究

发布时间：2017-09-21 22:22

  本文关键词：图的积和谱刻画问题研究

  更多相关文章： 积和式 积和多项式 积和谱 积和零度 积和同谱图 Gutman问题 特征多项式 邻接谱

【摘要】：图G的积和多项式由Merris等和Kasum等分别在数学和化学中几乎同时引入,它通过矩阵xI-A(G)的积和式(permanent)来定义,其中I和A(G)分别是单位矩阵和G的邻接矩阵.但Valiant证明了矩阵的积和式的计算是个轷P-完全问题.刻画哪些图类由其谱唯一确定是图谱理论中一个经典问题.van Dam和Haemers系统地研究了该问题,并猜想几乎所有的图都是邻接谱确定的.图的积和多项式的所有根(包含其重数)构成的重集称为图的积和谱Merris等首次提出了积和谱刻画问题,即什么样的图是积和谱确定的?图G是积和谱确定的是指任意与G有相同积和谱的图H,必有H同构于G.此外,他们认为除树外图的积和谱区分图比邻接谱要好一些.最近,柳顺义和张和平开始探讨了一些图类是否是积和谱确定的,证明了星图、完全图、完全正则二部图和奇圈是积和谱确定的.结果表明邻接谱确定的图不一定是积和谱确定的.两个图是积和同谱的是指它们有相同的积和谱.Borowiecki和Jozwiak最早考虑了积和同谱图的构造问题,主要探讨了哪些图对既是积和同谱的又是邻接同谱的.本文中,我们对图的积和谱刻画问题做了系统的研究.证明了完全图删一些边所得子图是积和谱确定的.特别地,我们引入了图的积和零度的概念,即,图的积和谱中零根的数目.利用图的积和零度参数,证明了具有极值积和零度的图是积和谱确定的,并证明了完全二部图是积和谱确定的.此外,借助图的积和零度和其匹配数之间的关系,证明了平衡完全二部图删一些边所得子图是积和谱确定的.最后,我们给出了一些构造图对既是积和同谱又是邻接同谱的方法.第一章介绍了图的积和多项式的研究背景.综述了图的积和多项式和积和谱的研究进展.第二章中我们以Merris等的看法为出发点探讨了哪些完全图删除一些特殊边所得的子图是积和谱确定的.证明了完全图至多删除五条边的所有子图都是积和谱确定的.而Camara和Haemers的结果表明这类图中恰有一对不能由邻接谱所确定.此外,还证明了完全图删一个星,一个匹配以及一个匹配和路P3的不交并的边所得的子图是积和谱确定的.第三章进一步证明了完全图删除六条边的所有子图是积和谱确定的,并考虑了邻接谱刻画问题.发现了任意图中长为4的闭途径与其积和多项式第四个系数之间的关系,并借助于该关系拓展了Camara和Haemers的结果,证明了完全图删六条边的所有子图中仅有两对邻接同谱图,即K5-E(K4)和K5-E(B),Kn-E(C6)和Kn-E(T2,2,2)分别是邻接同谱的,其中B是一个领结图,n≥7.第四章引入了图的积和零度的概念,并给出了它的一些基本性质.进而完全刻画了积和零度为n-2,n-3,n-4和n-5的图,其中n为图的顶点数.这些图恰好是仅有3,4,5或6个不同积和根的部分图类.利用积和零度参数,证明了积和零度为n-2,n-3,或n-5的图以及积和零度为n-4的非二部图是积和谱确定的.特别地,证明了完全二部图是积和谱确定的.第五章借助图的积和零度和匹配数之间的关系,证明了从平衡完全二部图Kp,p中删除一个星K1,l(lp)的边所得子图是积和谱确定的.此外,还证明了Kp,p删至多五条边的所有子图中满足其匹配数等于p的图是积和谱确定的.在第六章中我们探讨了哪些图对既是积和同谱的又是邻接同谱的.给出了一个构造方法,得到了无数对森林是这样的图.此外,借助图的粘接运算,可构造了无穷多对图是积和同谱的又是邻接同谱的.最后,我们证明了图G的积和多项式的导数等于其所有删一个顶点的子图的积和多项式之和.特别地,我们讨论并解决了关于图的积和多项式的Gutman问题.
【关键词】：积和式 积和多项式 积和谱 积和零度 积和同谱图 Gutman问题 特征多项式 邻接谱
【学位授予单位】：兰州大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要3-5
• 英文摘要5-10
• 第一章 引言10-26
• 1.1 基本概念10-12
• 1.2 图的积和多项式的研究背景12-15
• 1.3 图的积和多项式和积和谱的研究进展15-24
• 1.4 本文的主要研究结果24-26
• 第二章 完全图删除一些边所得子图的积和谱刻画26-40
• 2.1 准备知识26-29
• 2.2 完全图删除至多五条边所得子图的积和谱刻画29-37
• 2.2.1 两个重要引理31-34
• 2.2.2 主要结果34-37
• 2.3 完全图删除特殊边结构所得子图的积和谱刻画37-40
• 第三章 完全图删六条边子图的积和谱和邻接谱刻画40-62
• 3.1 明定理3.140-53
• 3.1.1 准备知识40-47
• 3.1.2 定理3.1的证明47-53
• 3.2 明定理3.253-60
• 3.2.1 一些引理53-55
• 3.2.2 定理3.2的证明55-60
• 3.3 结束语60-62
• 第四章 图的积和零度与具有极值积和零度图的积和谱刻画62-76
• 4.1 图的积和零度的一些基本性质62-64
• 4.2 刻画具有极值积和零度的图64-68
• 4.3 具有积和零度的图的积和谱刻画68-74
• 4.3.1 积和零度为n-2和n-3的图是积和谱确定的69
• 4.3.2 积和零度为n-4的非二部图是积和谱确定的69-72
• 4.3.3 积和零度为n-5的图是积和谱确定的72-74
• 4.4 完全二部图的积和谱刻画74
• 4.5 结束语74-76
• 第五章 平衡完全二部图删一些边所得子图的积和谱刻画76-92
• 5.1 平衡完全二部图删星所得子图是积和谱确定的76-78
• 5.2 平衡完全二部图删至多五条边的子图是积和谱确定的78-90
• 5.2.1 预备知识78-84
• 5.2.2 主要结果84-88
• 5.2.3 小结88-90
• 5.3 结束语90-92
• 第六章 积和同谱图与图积和多项式的Gutman问题92-102
• 6.1 构造既是积和同谱又是邻接同谱的图对92-97
• 6.1.1 一个构造方法92-95
• 6.1.2 粘接法的一个注记95-97
• 6.1.3 小结97
• 6.2 图积和多项式的Gutman问题97-102
• 6.2.1 图积和多项式的导数98-100
• 6.2.2 主要结果100-102
• 参考文献102-110
• 在学期间的研究成果110-112
• 致谢112

【相似文献】

中国期刊全文数据库 前9条

1 张钟嵊;利用对消法直接求网络图的树积和及副树积和[J];山东工业大学学报;1996年03期

2 彭求实;;一个关于积和的等式证明及其应用[J];哈尔滨商业大学学报(自然科学版);2008年03期

3 焦争鸣;王志更;;广义L-R Smash-积和L-R Smash-余积[J];河南师范大学学报(自然科学版);2008年01期

4 冯良贵,郝志峰;亚投射环的积和矩阵扩张(英文)[J];数学进展;2001年02期

5 李金其,许永华;辫子monoidal范畴中的Smash余积和辫子群[J];中国科学(A辑 数学 物理学 天文学 技术科学);1997年06期

6 郭艳苹;;正确使用积和商的定位公式是提高珠算技术水平的重要途径[J];北京农业工程大学社会科学学报;1994年Z2期

7 傅建民;一个不等式的加细[J];黔东南民族师专学报;1994年Z1期

8 宋善炎;纪风霞;;竞赛专题八 物体的性质[J];湖南中学物理;2010年09期

9 ;[J];;年期

中国博士学位论文全文数据库 前3条

1 吴廷增;图的积和谱刻画问题研究[D];兰州大学;2015年

2 柳顺义;关于图的积和多项式若干问题的研究[D];兰州大学;2013年

3 李巍;图的积和多项式及其相关问题[D];兰州大学;2012年

，

本文编号：897215