图的积和谱刻画问题研究

来源 :兰州大学 | 被引量 : 0次 | 上传用户:zdx_comeon
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图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(l<p)的边所得子图是积和谱确定的.此外,还证明了Kp,p删至多五条边的所有子图中满足其匹配数等于p的图是积和谱确定的.在第六章中我们探讨了哪些图对既是积和同谱的又是邻接同谱的.给出了一个构造方法,得到了无数对森林是这样的图.此外,借助图的粘接运算,可构造了无穷多对图是积和同谱的又是邻接同谱的.最后,我们证明了图G的积和多项式的导数等于其所有删一个顶点的子图的积和多项式之和.特别地,我们讨论并解决了关于图的积和多项式的Gutman问题.
其他文献
本文主要研究两个具有吸引相互作用的量子系统:Bose-Einstein凝聚和玻色星体系统.前者为非相对论量子系统,在数学上可以用Gross-Pitaevskii能量泛函来描述;而后者为近似相对论量子系统,在数学上可以用近似相对论Hartree能量泛函来描述.我们分别考虑了 M2中Gross-Pitaevskii能量的极小化问题和R3中近似相对论Hartree方程能量的极小化问题.首先,我们将Guo
本文主要研究奇异非线性椭圆型方程Dirichlet问题的古典解在边界附件的精确渐近行为.这里,Ω是RN中的有界光滑区域,λ,μ,σ≥ O,q∈(0,2],b,a∈Cloca(Ω)(0<α0,使得对任意的s∈(0,s0)有g’(s)<0.首先,对于问题我们在边界附近建立
本文主要研究了自由对合Hom-结合代数,罗巴算子和罗巴型算子的分类,全文共分为六章.第一章介绍了本文研究课题的背景及其进展,并给出本文需要的基本概念和一些相关的记号,然后分析了本文的研究动机.第二章首先引入了Hom-半群的概念,并给出例子说明半群类是Hom-半群类的真子类.然后借助括号字构造了自由对合Hom-半群,从而得到集合上的自由对合Hom-结合代数的显性构造.第三章主要研究了自由算子半群中括
学位
本文主要研究如下定义在非柱形区域上的非自治反应扩散方程解的长时间行为:其中非线性函数g(·)满足任意阶多项式增长条件.由于空间区域随时间变化,上述系统具有某种非自治固有性-即使外力项f(·)不显含时间t,上述方程仍是非自治的.我们的主要工作是建立新的方法(框架)和先验估计,对非线性项及外力项不增加任何额外假设,特别地,对外力项不做任何光滑性假设,证明已知的(L2,L2)型拉回(?)-吸引子事实上可
作为量子物理学的重要模型之一,描述原子核内部核子和介子之间的相互作用的Klein-Gordon-Schrodinger(KGS)系统不仅揭示着现代物理学中最深刻的粒子运动规律.同时,作为一类重要的混合型偏微分方程组,它也成为引领现代数学的重要研究方向.近年来学者们对其进行了广泛的研究并取得丰硕成果.随着研究的深入,各种复杂环境下的KGS系统被相继导出并再次引起广泛关注.然而已有的结果大多集中于耗散
图的控制数是图的基本的不变量之一,也是反映网络性能的一个参数.图的约束数是指让图的控制数增大所需删除的最少边的数目.它能衡量在通信线路发生故障情况下互联网络脆弱性.然而,图的控制数和约束数的计算已经分别被证明是NP-完全和NP-困难问题.许多学者都致力于图的最小控制集与最小约束边集的结构和性质的研究,以及计算特殊图类的控制数与约束数的精确值或者给出它们界.一般来说,计算一个图的约束数比计算其控制数
反应扩散方程作为一类特殊类型的抛物型方程,它是用来研究自然界中广泛存在的扩散现象的有力工具.例如,物理学中的热传导现象、燃烧理论中的燃烧温度问题、化学反应中的物质浓度变化、生态学中的物种入侵过程以及疾病在空间中的传播等都可以用一个反应扩散方程来描述.行波解作为反应扩散方程的一类特殊形式的解,它能够很好地解释自然界中的振荡现象以及有限速度传播等问题,因此,一维行波解的存在性、唯一性和稳定性被人们所广
云和气溶胶的辐射效应是气候系统中最不确定的因素之一,沙尘气溶胶作为主要的气溶胶类型在全球能量平衡中扮演着重要的角色,因此准确区分大气中的云和沙尘气溶胶对于减小气候系统的不确定性具有非常重要的意义。以往的研究大多将沙尘简单的当作自然气溶胶,关于人为沙尘方面的观测研究非常缺乏,其在大气中所占的比例、辐射强迫以及对气候变化的影响等更是存在很大的不确定性。因此迫切需要相关观测资料和识别方法来改进对人为沙尘
"三味书屋"和"百草园"是绍兴市鲁迅小学语文项目化学习的两个课程用词,取自鲁迅先生的《从百草园到三味书屋》。"百草园"式的儿童课程里没有半分压抑的痕迹,有的只是自然状态下自由自在、无拘无束的童真游戏。"三味书屋"的况味则完全不同,它是"严厉的书塾",有很多规矩束缚,具有传统学校课程的特征。我们带着学生阅读鲁迅作品,从"三味书屋"式的课程出发,用"百草园"的方式来进行。不管是哪个层次的儿童,
期刊