硼氮富勒烯图的反强迫数

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

环状fibonacene六角链的反强迫数

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

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

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

修正泡型图的条件匹配排除

一个图G的条件匹配排除数是最少的边的数量,使得删去这些边后形成的图既没有孤立点也没有完美匹配和几乎完美匹配.任何一个这样的边集称为G的一个最优条件匹配排除集.条件匹配排除数是衡量网络在边故障情况下的鲁棒性的参数之一.主要给出了修正泡型图的条件匹配排除数是2n-2(n≥5).     

单圈图的k-距离匹配控制数

单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(G)是G的一个k-距离控制集且导出子图〈D〉有完美匹配,则称D是G的一个k-距离匹配控制集.k-距离匹配控制数γkp(G)是G的最小k-距离匹配控制集的势.主要证明了单圈图k-距离匹配控制数的一个重要引理,由此找到了单圈图k-距离匹配控制数的上界,并构造了极图.     

3元立方体的匹配排除

设E是图G的一个边子集,若G-E中既没有完美匹配也没有几乎完美匹配,则称E为G的一个匹配排除集.边数最少的匹配排除集的基数,称为图G的匹配排除数.文章给出了3元立方体的最优匹配排除数.     

PM紧邻极值Brick

图G中所有完美匹配的关联向量,通过整数线性组合形成的空间,称为图的匹配格.若匹配覆盖图满足G完美匹配数等于匹配格的维数,则称其为匹配覆盖极值图.当图任意去掉两个点不交的匹配交错圈后,剩下的图无完美匹配,则称该图满足PM紧邻.本文证明了所有极值brick均为PM紧邻.     

k元n方体的最优条件匹配排除集

设E是图G的一个边子集,若G-E中既不包含孤立点,也没有完美匹配和几乎完美匹配,则称E为G的一个条件匹配排除集.边数最少的条件匹配排除集,称为最优条件匹配排除集.文章给出了k元n方体的最优条件匹配排除集.     

关于完美匹配的一个注记

图G有完美匹配当且仅当对于其顶点集V的任意子集S，G－S的奇分支的个数不超过S中元素的个数。对此结论证明中存在的一个问题进行了详细讨论，从而使证明更加完善。     

链状四角系统及其完美匹配数

研究了链状四角系统的构成,定义了构成渺位四角系统的3种运算,并讨论在不同四角运算下链状四角系统的完美匹配数,进而讨论了链状四角系统按其完美匹配数由小到大的排序问题.     

Cn×P2的2-偶匹配可扩性

称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V（M）]是偶图称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中为了进一步地研究图的偶匹配可扩性,我们考虑图G的偶匹配数,即图G中最大偶匹配所含的边数,记为BM（G）,我们证明了Cn×P2是2-偶匹配可扩的。     

图有较高连通度的一个充要条件

图的连通性理论是图论学科重要而基础的研究领域,通过该领域的研究,人们对图的结构和性质有了进一步的认识,并且将所得到的结果应用于网络设计、城市交通等实际问题中,取得了很多应用成果,例如,量化一个图或网络的脆弱程度,便始于图的连通性研究。因此,我们总是希望图能具有较高的连通度。对n个顶点的图G来说,当连通度不小于顶点数n的一半时,我们认为这个图有较高的连通度。本文试图给出图具有较高连通度的一个充分必要条件。我们指出,对一个给定的正整数k且k≤2n,有κ(G)≥n-k成立当且仅当对顶点集V(G)的任意一对不交子集S和T,G[S,T]有一个完美匹配,这里|S|=|T|=k,G[S,T]=G[S∪T]-E(G[S])-E(G[T])。     

具有完美匹配图的一个新特征

0 引言 [1]中指出,一个图G什么时候有一个完美匹配?这个比较困难的问题在1947年为加拿大著名图论学者托特(Tutte)所解决。托特所给出的具有完美匹配的图的特征是用G的奇支来描述的。G的一个奇支,是指图G的一个支中有奇数个点。G中奇支的数目记作oc(G)。于是,一个图G有一个完美匹配当且仅当对任何S(G),有oc(G-S)≤|S|。本文利用文[2]提出的“等秩变换”,     

4元n方体的匹配图的若干性质

一个图G的匹配图M(G)的顶点集是G的所有完美匹配的集合,两个顶点相邻当且仅当对应的两个完善匹配的并构成G的一个Hamilton圈.文章给出了4元n方体Qn4的匹配图M(Qn4)的一些性质.     

关于偶匹配可扩图中删去两个点

设G是含有完美匹配的简单图.称G是偶匹配可扩的,如果G中导出子图是偶图的匹配M都可以扩充为G的完美匹配.研究了在偶匹配可扩图中删去两个顶点后该图的性质.这些性质对于偶匹配可扩图的进一步研究会有帮助.     

一类乘积图的Pfaffian性

给图G的边任意一个定向,如果该有向图对应的斜邻接矩阵的行列式等于图G的完美匹配数的平方,那么就称这个定向是Pfaffian定向,图G称为Pfaffian图.研究Pfaffian图的意义在于它的完美匹配数能在多项式时间内得到.该文通过证明给出的定向是Pfaffian定向的方法证明了一类偶剖分图与三个顶点的路的乘积图是Pfaffian图.     

路径幂图、Flower Snark图及多锥图独立数

图的独立数是图论中的重要参数,令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记做α(G).研究了路径幂图、Flower Snark及其相关图、多锥图的独立数问题,首先构造出了它们的独立集,得到其独立数的下界,然后证明了该值也是其独立数的上界,并给出了它们独立数的准确值.     

一类笛卡儿乘积图的PM-紧邻性质

图G的完美匹配图,记为PM(G),是以G的每个完美匹配作为顶点并且两个顶点相邻当且仅当这两点对应于G中两个完美匹配的对称差恰好是一个圈而得到的图.若PM(G)是完全图,则称G是完美匹配紧邻的,简称G是PM-紧邻的.研究了一类笛卡儿乘积图的PM-紧邻性质,完全刻画在这类笛卡儿乘积图中所有的PM-紧邻图.     

二部图匹配的一个判别条件

根据Hall定理,二部图G=(V1,V2;E)有一个浸润V1匹配的充要条件是:SV1,N(S)∩V2≥S,即V2中与V1的任一子集S相邻的顶点数不小于S中的顶点数。当V1中的顶点数较多时,用该条件判定较为困难。本文给出了一个基于顶点度判别二部图有浸润匹配的条件,并应用该条件解决了一个关于图的二划分的问题。     

无三角形3-正则图的几个参数的界

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G 中的一个两两不相邻的边子集称为图G 的一个匹配。图G 的一个最大匹配的边数称为图G 的匹配数。图G 中的一个与G 的每个团都有交的顶点子集称为G 的一个团横贯集,图G 中元素个数最少的团横贯集的顶点数称为G 的团横贯数。本文针对n阶连通无三角形的3-正则图G=(V(G),E(G)),首先给出了其割边数的一个上界(n-10)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13|E(G)|+3)/36。同时刻画了达到这些界的极值图。