图的多项式唯一性

论文摘要

多年来,图多项式一直是一个活跃的研究课题,它在图论与传统代数之间架起了桥梁。因为图多项式的系数包含了丰富的组合信息,所以图多项式的研究为我们了解图的复杂结构与参数提供了新的途径。一个很自然的问题就是什么类型的图能被它们的多项式唯一确定?特别地,什么类型的图,它的结构可以被一个图多项式完全刻画?换句话来说,我们是否可以找到一类图使得他们可以被一个给定的多项式所确定?本文主要研究这些问题。图论中有三个重要的多项式:色多项式、Tutte多项式以及流多项式。这三个多项式有很密切的关系,其中色多项式与流多项式在某种意义上具有“对偶性”,并且它们都是Tutte多项式的特殊形式。色多项式以及能够由色多项式唯一确定的图等问题已得到深入研究,近些年,更多研究关注于Tutte多项式以及能够由Tutte多项式唯一决定的图。然而,关于流多项式,这方面的成果还屈指可数。另外,关于能被色多项式与流多项式所共同确定的图方面的研究还是空白。本论文首次对这些问题进行了研究。论文结果包括两个方面的内容。第一部分主要是对流多项式的研究以及能被色多项式与流多项式共同确定的图的研究;第二部分主要涉及能被Tutte多项式所唯一确定的图的研究。论文的第一部分包括第二章和第三章。在第二章中,我们主要关注图的流多项式。我们研究了流多项式的系数,并且证明:若两个连通的对偶简单图有相同的流多项式,那么他们有相同的点数、边数、边连通度以及相同数目的最小边割。利用这些信息,我们得出了广义θ-图的对偶图、5个顶点的完全图K5以及六个顶点的完全二部图K3,3是可以被它们的流多项式所唯一确定的。在第三章中,我们综合运用包含在色多项式与流多项式中的信息,证明了梯子、M（?）bius梯子以及圈平方图可以被它的色多项式和流多项式所共同决定。而这几类图,de Mier和Noy曾证明它们是能被Tutte多项式所唯一确定的,这个结果可以看作是我们结论的推论。第二部分即第四章。在这一章中,我们研究了两类图:第一类图我们称作是“曲轮”,记作Wk1,k2（见图4.2）,第二类图与曲轮有着相似的结构,我们称之为“双半轮”Wh（k1,k2）（见图4.3（b））。为简化这两类图的结构,我们首次引入了“三角-图”的概念,这个概念的思想与线图有一定的相似之处。我们通过综合运用包含在Tutte多项式中的信息证明了这两类图是可以被Tutte多项式所唯一确定的。

论文目录

• Abstract in Chinese
• Abstract
• 1 Introduction
• 1.1 Notation and terminology
• 1.2 On polynomials of graphs
• 1.3 Relations of the three polynomials
• 2 Flow polynomial and flow-uniqueness of graphs
• 2.1 The coefficients of the flow polynomials of graphs
• 2.2 Information contained in flow polynomials of graphs
• 2.3 Flow-unique graphs
• 2.4 Conclusion and expectation
• 3 （P, Q）-uniqueness of graphs
• 3.1 Preliminaries
• 3.2 Ladders and Mobius ladders are （P, Q）-unique
• 3.3 Cycle squares are （P, Q）-unique
• 3.4 Conclusion and expectation
• 4 T-uniqueness of graphs
• 4.1 Basic definitions and notations
• 4.2 The triangle-graph of a graph
• 4.3 The proof of the twisted wheels are T-unique
• 4.4 The proof of the double half-wheels are T-unique
• 4.5 Conclusion and expectation
• Bibliography
• 致谢
• 个人简介