图的多项式唯一性

来源 :南开大学 | 被引量 : 1次 | 上传用户:tvxq905
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
多年来,图多项式一直是一个活跃的研究课题,它在图论与传统代数之间架起了桥梁。因为图多项式的系数包含了丰富的组合信息,所以图多项式的研究为我们了解图的复杂结构与参数提供了新的途径。一个很自然的问题就是什么类型的图能被它们的多项式唯一确定?特别地,什么类型的图,它的结构可以被一个图多项式完全刻画?换句话来说,我们是否可以找到一类图使得他们可以被一个给定的多项式所确定?本文主要研究这些问题。   图论中有三个重要的多项式:色多项式、Tutte多项式以及流多项式。这三个多项式有很密切的关系,其中色多项式与流多项式在某种意义上具有“对偶性”,并且它们都是Tutte多项式的特殊形式。色多项式以及能够由色多项式唯一确定的图等问题已得到深入研究,近些年,更多研究关注于Tutte多项式以及能够由Tutte多项式唯一决定的图。然而,关于流多项式,这方面的成果还屈指可数。另外,关于能被色多项式与流多项式所共同确定的图方面的研究还是空白。本论文首次对这些问题进行了研究。   论文结果包括两个方面的内容。第一部分主要是对流多项式的研究以及能被色多项式与流多项式共同确定的图的研究;第二部分主要涉及能被Tutte多项式所唯一确定的图的研究。   论文的第一部分包括第二章和第三章。在第二章中,我们主要关注图的流多项式。我们研究了流多项式的系数,并且证明:若两个连通的对偶简单图有相同的流多项式,那么他们有相同的点数、边数、边连通度以及相同数目的最小边割。利用这些信息,我们得出了广义θ-图的对偶图、5个顶点的完全图K5以及六个顶点的完全二部图K3,3是可以被它们的流多项式所唯一确定的。   在第三章中,我们综合运用包含在色多项式与流多项式中的信息,证明了梯子、Mobius梯子以及圈平方图可以被它的色多项式和流多项式所共同决定。而这几类图,de Mier和Noy曾证明它们是能被Tutte多项式所唯一确定的,这个结果可以看作是我们结论的推论。   第二部分即第四章。在这一章中,我们研究了两类图:第一类图我们称作是“曲轮”,记作Wk1,k2(见图4.2),第二类图与曲轮有着相似的结构,我们称之为“双半轮”Wh(k1,k2)(见图4.3(b))。为简化这两类图的结构,我们首次引入了“三角-图”的概念,这个概念的思想与线图有一定的相似之处。我们通过综合运用包含在Tutte多项式中的信息证明了这两类图是可以被Tutte多项式所唯一确定的。
其他文献
学位
从蓝藻到人类,几乎所有生物体的生理、代谢活动和行为过程都表现出以24小时为周期的昼夜节律性.人们最熟悉的昼夜节律是每天的睡眠—觉醒节律.此外,人体的其它生理功能,如体温、
本文研究的是集值随机过程关于时间变量t的Lebesgue积分,Aumann型Lebesgue积分,和集值Ito型随机微分方程. 本文分为三部分: 第一部分是闭集值随机过程关于时间变量t的Leb
网络思想教育环境对大学生的政治立场、道德观、价值观等的塑造和培养有着重要的作用,通过对网络思想教育环境的概念、特点和结构的厘清,结合当前大学网络思想教育环境存在的
正交表不仅在统计上非常有用,还被广泛应用于密码学、编码学、计算机科学等.正交表在数据处理中起着重要作用,对于不同的实际问题,需要用不同类型的正交表进行设计和分析.为了有
健康不公平是指在个体之间或人群组别之间,存在着可避免的或不公正的健康状态及危险因素或卫生服务利用上的不平等.这种不合理的不平等就是健康不公平.通过卫生服务利用与健
在本文中,我们主要研究了两个结果.结果一,在一致光滑、严格凸、含有Kadec-Klee性质的实Banach空间E中给出了一种新的迭代格式,用于逼近一族依中间意义渐近严格拟φ-伪压缩映像
计算机网络的快速发展和多媒体技术的广泛应用使越来越多的数字图像通过各种媒介传输.由于数字图像数据所具有的大数据量特点,传统的加密方法如DES、AES和RSA并不完全适合直
图的控制参数理论是由Berge和Ore共同建立的.Ore使用目前一直沿用的控制数方面的术语dominating set和domination number.Cockayne和Hedetnieni概述了图的控制理论结果,并开始
本文主要研究广义Boussinesq方程组解的局部适定性和正则性准则.全文共分三章.  第一章介绍研究的背景和意义,回顾了有关广义Boussinesq方程组的一些研究结果,基本记号以及本