一类碳纳米管状图的Tutte多项式

给出了一类管状图的Tutte多项式的一个算法，这类图的形状与碳纳米管类似。找到了这类图在删除—限制算法中的基图，用基图的Tutte多项式给出了管状图的Tutte多项式的递推公式，用Maple实现了管状图的Tutte多项式的计算。     

一类图构形的Orlik-Solomon代数及Tutte多项式

研究得到了n-秩轮图及其导出图构形的Orlik-Solomon代数的计算公式,n-秩轮图关于某条边的删除B_n以及n-秩轮图的Tutte多项式的一般表达式,并计算了n-秩轮图（n=5,6）的双变量着色多项式,举例说明图的双变量着色多项式与Tutte多项式是不相同的。     

Orlik-Solomon代数的NBC基的一个算法

文中给出了Orlik-Solomon代数NBC基的一个算法,并在计算机上进行了实现。用此算法对顶点数小于7的带号完全n点形图构形做了π-分类,计算了各类的Poincaré多项式。最后,给出猜想“带号完全n点形的相反图构形A(G)是不自由的,则完全n点形图构形A(G)是自由的”的一个反例。     

图的多项式不变量的一个推广

图论中的一个核心问题是研究图的不变量.对于给定的一个平图,可以建立该图的Tutte多项式不变量.一直以来,认为Tutte多项式是最一般的图的不变量.经典的Tutte多项式不变量是含有2个变元x,y的多项式,但是这个多项式却不能区分所有的图.这促使我们考虑可以通过增加变元的方法来细分图的类别.对于给定一个的平图,将图的Tutte多项式不变量进行了推广,得到一个新的n变元多项式,并证明其是图的不变量.进而,也验证它能区分Tutte多项式不能区分的一类图,这类图是给定的一个图与在这个图上再加一些与之不相交的点.     

基于平图的两种有向链环的Homfly多项式

给定一个平图,Jaeger为之联系了一个有向链环,并建立了该图的Tutte多项式和所得有向链环的Homfly多项式之间的关系.这促使我们考虑其它给图联系有向链环的方式并得到类似的关系.文中给定一个平图,通过其中间图构造了两种有向链环,得到了这两种有向链环的Homfly多项式和该图的Tutte多项式之间的关系,其中一个关系推广了Jaeger的工作.根据上述得到的两个关系,给出了两类有向链环的Homfly多项式.     

关于D-图的注记

为了研究具有完美匹配图的Tutte集和极端集,D Bauer等提出了一种新的图运算D-图,并且得到许多有趣的性质.本文研究了基本图的水平,证明了对于任何非二部的基本图,它的D~2(G)是一个完全图.此外,还给出了饱和图G的D-图的刻画,并且对于一般图的情形做出了分析.     

强连通强符号非异带号有向图的特征刻画

强符号非异矩阵 (简称S2 NS矩阵 )在定性矩阵理论的研究中有重要意义 .据此研究与S2 NS矩阵直接相关的S2 NS带号有向图的特征刻画问题 .一个带号有向图S称为是S2 NS带号有向图 ,若S中所有圈的符号均为负 ,且S中任意两条同始同终的路均同号 .注意到在此定义中所涉及到的两个条件都不能用多项式算法来进行验证 .这里首次给出强连通情况下S2 NS带号有向图S的一个可以用多项式算法进行验证的特征刻画     

Polya公式与色轨道多项式

色轨道多项式是色多项式与Ｐｏｌｙａ计数公式的推广，本定义了色轨道多项式及其相应的概念加Ｐ－图，ＳＣ－图等，给出了色轨道多项式的表达式和计算方法，讨论了色轨道多项式的基本性质，作为它的一个应用，给出了项链问题的具体计数公式。     

Tutte定理与Tutte-Berge公式的等价性证明

Tutte定理在匹配理论中占有中心位置,刻画了一般图有完美匹配的充分必要条件.Tutte-Berge公式是任意图上关于最大匹配的一个核心结果,确定了匹配数的一个最大最小关系,且提供了任意图中匹配数的一个紧的上界.Tutte定理常常被认为是Tutte-Berge公式的一个特殊情形.提供Tutte定理与TutteBerge公式的一个简单而完整的等价性证明,从而说明Tutte-Berge公式也是Tutte定理的一个特殊情形.作为Tutte公式的一个应用,考察并总结了任意正则图中是否具有完美匹配的情况,结果包含了著名的Petersen定理.     

Pólya公式与色轨道多项式

色轨道多项式是色多项式与 Pólya计数公式的推广 .本文定义了色轨道多项式及其相应的概念如 P-图 ,SC-图等 ,给出了色轨道多项式的表达式和计算方法 ,讨论了色轨道多项式的基本性质 .作为它的一个应用 ,给了项链问题的具体计数公式     

关于图的强符号控制数的下界

图G的强符号控制数γss(G)有着许多重要的应用背景,因此确定其下界有重要意义.本文在图的符号控制数基础上对图的强符号控制数进行了研究,指出了文献[3]定理5的小错误,改进了文献[4]定理4的下界,给出了图的强符号控制数的3个独立的下界,并给出了达到这3个下界的图.     

符号图的特征多项式系数定理及其应用

将简单图的邻接矩阵的特征多项式系数定理推广到适合符号图的情形,并将其用于研究n阶单圈符号图的零度。当$n\geq 5$时,得到了它的上界为n-4,并刻画了零度为n-4的图;得到了单圈符号图的零指数集合．     

关于正则图的符号边控制数

本文讨论了正则图的符号边控制数并确定了一般正则图的符号边控制数的上、下界,进而给出了达到下界的必要条件同时构造出达到下界的特殊图.     

具有第四大和第五大谱半径的n阶2-树

G为n阶的2-树,首先应用边移接变形的方法得到关于图G谱半径的一个判定定理,又通过比较一些图的特征多项式,刻画出该图类的谱半径达到第四大和第五大的极图.     

几类图的符号星k控制数

通过对图G的边集分析的方法,对图的符号星k控制数进行研究,确定了几类图的符号星k控制数     

Dn型通有构形的特征多项式

设W是n维欧氏空间中的D_n型Weyl群,以W的正根为法向量的超平面形成的通有构形称为D_n型通有构形,记为A(D_n)。首先建立了不含自环的符号图与A(D_n)的子构形的一一对应关系;其次,研究了一个符号圈线性相关的充要条件;最后从符号图的角度给出A(D_n)的子构形线性无关的充要条件。在此基础上,给出A(D_n)及其子构形的特征多项式的具体计算方法。     

图8.8.4格的链环分支数

链环分支数与符号平图之间有一一对应关系,这种对应是通过中间图来实现的,它提供了通过图研究链环的一个方法.在二十世纪八十年代末,这一对应就被用于建立纽结理论中的琼斯多项式的关系,但链环分支数与对应平图的符号无关,链环分支数是链环的最简单的一个不变量,求符号平图对应链环分支数是通过平图研究链环的最基本的问题之一,本文确定了8.8.4格的链环分支数.     

四叶图距离矩阵2个最大特征值和的变化

为了能够在任何情况下准确得到四叶图在2种图变换下距离特征值的极值,运用行列式的性质、韦达定理及不等式的放缩,给出了四叶图的2种图变换及上述问题的结果。首先分别给出变换前后3种四叶图距离矩阵、距离拉普拉斯矩阵及距离无符号拉普拉斯矩阵,利用行列式的性质计算得出其特征多项式,由韦达定理判断出3种距离特征多项式正负根的个数,通过不等式的放缩估计出特征值的范围,从而求出2个最大特征值和的范围;其次对变化前后四叶图的3种距离矩阵2个最大特征值的和进行比较。结果显示,四叶图在经过2种变换后2个最大特征值的和是增加的。所得结果为特殊图类距离特征值极值问题提供了研究方法,对分子稳定性问题的研究具有一定的借鉴价值。