单圈图的零强迫数的极小值

证明单圈图G满足Δ(G)-2≤Z(G)≤P(G)+2,并刻画了满足Z(G)=Δ(G)-2的所有单圈图,其中Δ(G)和P(G)分别表示图G的最大度和悬挂点的数目.

双圈图的零强迫数与一般位置数

设F(G)是图G的零强迫数,gp(G)是图G的一般位置数。注意,gp(G)≥F(T)+1对所有树T都成立。Hua等人在中证明了此结果可以扩展到块图,并证明了对于连通单圈图G,gp(G)≥F(T)。在本文中,我们刻画了使得gp(G)≥F(T)成立的双圈图的结构。

硼氮富勒烯图的反强迫数

设G是一个有完美匹配的图。若G的边集S满足G-S有唯一完美匹配,则称S为反强迫集。包含边数最少的反强迫集叫做极小反强迫集,其中边的数目叫做图G的反强迫数。本文主要解决硼氮富勒烯图(恰好有六个四边形面,其它面都是六边形,3-连通的平面二部图)的反强迫数。我们得到一类管状,环边连通度为3的硼氮富勒烯图的反强迫数,然后得到任何硼氮富勒烯图的反强迫数至少为3,进而构造出所有反强迫数为3的硼氮富勒烯图,共有两个。

圈和路的笛卡尔积的H-强迫数

通过研究笛卡尔积的定义得到了圈和路作笛卡尔积后得到的图形,探讨了所得图形的H-强迫集与H-强迫数问题.利用寻找非哈密尔顿圈的方法证明了主要结论:设Ck表示k个顶点的圈,Pl表示l个顶点的路,G=Ck×Pl表示Ck与Pl的笛卡尔积.则当k为偶数时,图G的H-强迫数为kl2;当k为奇数时,图G的H-强迫数为kl.

二部克莱茵瓶六角系统K(p,q,t)的强迫数I.p≤q或q

能惟一确定图G的完美匹配M的最小不交边子集所含的边数称作完美匹配M的强迫数.完美匹配强迫数在有机化学上也称作凯库勒结构的原始自由度,来源于对分子共振结构的研究,是化学分子图的一个重要拓扑不变量.给出了二部克莱茵瓶六角系统K(p,q,t)的强迫数下界,并表明当p≤q时,K(p,q,t)的最小强迫数为p;若q<p≤2q,K(p,q,t)的最小强迫数为q.

链状卡塔型苯图的反强迫数

设G是一个有完美匹配M的图.若G的边集S满足G-S有唯一完美匹配,则称S为反强迫集.包含边数最少的反强迫集叫做极小反强迫集,其边的数目叫做图G的反强迫数.DamirVukiěevi?等曾给出链状卡塔型苯图的反强迫数,但我们发现该结论存在问题,本文修正了并完善了链状卡塔型苯图的反强迫数.

二部克莱因瓶六角系统K(p,q,t)的强迫数Ⅱ.p>2q

二部克莱因瓶六角系统K(p,q,t)是嵌入到不可定向曲面克莱因瓶上的每个面的边界都是6长圈的二部图,匹配强迫数是有完美匹配图的一个重要拓扑不变量.通过考察克莱因瓶上不可收缩圈的新技术,给出了二部克莱因瓶六角系统K(p,q,t)(p>2q)的最小匹配强迫数的界.

关于Cm × Pk的反强迫数

设G 是一个有完美匹配的简单连通图。若G 的一个边子集S 满足G-S 只有唯一完美匹配,则称S 是G 的一个反强迫集。G 中最小的反强迫集的大小称为G 的反强迫数。本文主要研究圈和路的卡什积图的反强迫数。根据一个图有唯一完美匹配的必要条件,我们证明了C3&#215;P2k,C2K+1&#215;P2,C4&#215;P 的反强迫数都为k+1,并表明了C2k&#215;P2 (k≥2) 的反强迫数恒为3。

一般环状六角链的反强迫数

设S是E(G)的一个子集,如果G-S具有唯一的完美匹配,那么称S为G的一个反强迫集.G的最小反强迫集的大小称为G的反强迫数,记为af(G).分别给出段数为偶数及段数为1,3的一般环状六角链的反强迫数.

一些特殊图的最大匹配的强迫数

设M是图G的一个最大匹配,S是M的一个子集.如果S除了被M包含而不被图G的其他最大匹配所包含,那么称S是M的一个强迫集.M的最小强迫集所包含的边数称作M的强迫数,记为fM(G,M).图G的所有最大匹配的强迫数的最小值称为图G的最小强迫数,记作fM(G).本文给出了一些特殊图类的最大匹配的强迫数的确切值.

螺旋六角para-链的最大匹配的强迫数

令M是图G的一个最大匹配,S是M的一个子集。如果S除了被M包含而不被G的其它最大匹配所包含,那么称S是M的一个强迫集(forcing set)。M的最小强迫集所包含的边数称作是M的强迫数(forcing number),记为fm(G, M)。图G的所有最大匹配的强迫数的最小值称为G的最小强迫数(Minimum forcing number),记作fm(G)。在本文中,我们给出了螺旋六角para-链的最大匹配的强迫数的确切值。

删边梯子图和“L”型梯子图的反强迫数

通过分类计算的方法得到了删边梯子图的反强迫谱,进而得到了“L”型梯子图的反强迫数,过程中得到了斐波那契数列的一个组合证明。

环状fibonacene六角链的反强迫数

设S是E(G)的一个子集,如果G-S具有唯一的完美匹配,那么称S为G的一个反强迫集。G的最小反强迫集的大小称为G的反强迫数,记为af(G)。我们给出含n个六边形的环状fibonacene六角链的反强迫数。

六角系统图的BEC码和反强迫数

一个六角系统可以由它的边界的形状唯一确定,表示为边界边码,简称BEC码。若连通图G的边子集S满足G-S有唯一的完美匹配,则称最小的S的基数为图G的反强迫数。给出了一个算法,可以运用BEC码计算六角链的反强迫数。

零强迫数为最大度的树图

研究树图的零强迫数与其最大度的关系,刻画了零强迫数为最大度的所有树图.

二部图匹配强迫数的谱

改进了Riddle的尾点法,得到自然数k属于二部图匹配强迫数谱的必要条件,给出了二部图的最小强迫数等于一个颜色集所有规范序最小尾点数的充要条件。

关于矩形和斜带模型的反强迫数和反凯库勒数

在苯类化合物的凯库勒结构的研究中引入了反强迫数和反凯库勒数.通过分析矩形和斜带模型苯类化合物的分子图的结构,证明了具有k行l列的矩形R[k,l]和斜带模型Z[k,l]的反凯库勒数是2,R[k,l]的反强迫数是l,Z[k,l]的反强迫数不超过[(l+1)/2],其中[x]表示不超过x的最大整数.

循环梯状图的完美匹配的反强迫谱与卢卡斯数列

得到了循环梯状图的反强迫谱及其连续性,并给出了卢卡斯数列的两种组合解释.

梯子图完美匹配的反强迫谱与斐波那契数列

梯子图L n是路P n和P 2的笛卡尔积.利用1个分解定理,将L n的1个完美匹配的反强迫数分解为各个片段对应完美匹配的反强迫数之和,进而得出了梯子图L n的反强迫谱并证明了其连续性.通过对梯子图L n的所有完美匹配进行了分类计数,从而得到了关于斐波那契数列的2个组合解释.

六个苯环生成的六角系统的自由度

设 M 是图 G 的一个完美匹配,S 是 M 的一个子集。 若 S 不被 G 中其它完美匹配所包含,则称 S 是 M 的一个强迫集。 包含边数最少的强迫集的势称为 M 的强迫数,图 G 中所有完美匹配的强 迫数的和称作图 G 的自由度。 图的强迫多项式是最近提出的刻画全体强迫数分布的一种计数多项 式。 在本文中,利用强迫多项式,计算了所有由六个苯环生成的六角系统的自由度,井对比了它 们的平均自由度。