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

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

一类乘积图的Pfaffian性

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

3元立方体的匹配排除

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

6连通图完美匹配上的可收缩边

采用分类讨论的方法,研究了6-连通图中可收缩边在完美匹配上的分布情况,得到了如下新结果.设G是阶大于12的6-连通图,M是G的一个完美匹配,若图G的任意断片的阶都大于3,则M上至少有2条可收缩边.     

循环图C_(2n)(1,3)的2-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的.     

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

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

PM紧邻极值Brick

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

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

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

结合图的导出匹配可扩性

简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.     

蛛网图的偶匹配可扩性(英文)

图G的匹配M是偶匹配,如果G[V(M)]是偶图.图G是k-偶匹配可扩的(1≤k≤(V(G)-2)/2),如果G的每一个基数不大于k的偶匹配都可以扩充为G的一个完美匹配.研究蛛网图的偶匹配可扩性得出的结论是:蛛网图不具有偶匹配可扩性和2-偶匹配可扩性.     

导出匹配可扩图的度和条件(英文)

称一个简单图G是导出匹配可扩的,缩写为IM-可扩的,如果G的每一个导出匹配都包含在一个完美匹配中.研究导出匹配可扩图的度和条件,主要结果如下     

关于几乎k-可扩图的若干结论

设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性.     

循环图C_(2n)(1,4)的偶匹配可扩性

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,根据图的k-偶匹配可扩性完全刻画了循环图C2n(1,4)的偶匹配可扩性.     

k-正则图的可扩性质

设G是k正则（k-1）－边连通的简单图，F是G的一个边集且|F|≤k-1。本文证明了如下结论：如果G有完美匹配，则G－F也有完美匹配。于是，我们推出：如果G有完美匹配，则G是1－可扩图。     

硼氮富勒烯图的反强迫数

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

直径为2的无爪图的导出匹配可扩性

如果简单图G的每一个导出匹配都包含在它的一个完美匹配中，称图G是导出匹配可扩的，简称为IM-可扩的。研究了直径为2的无爪图的导出匹配性，证明了一个直径为2的无爪图G是IM-可扩的充分必要条件是：对任意满足|M|≤3的导出匹配M，G—V(M)没有奇分支。因而，直径为2的无爪图的IM-可扩性问题是多项式可解的。     

准可扩图的一些性质质

设 G是一个有限的简单连通图及其具有一个最大匹配 M*。 G称为是 n-可扩的 (1≤ n≤ |M*|- 1)如果 G的任一基数为 n的匹配都能扩充到 G的一个最大匹配 .特别地 ,当 G没有完美匹配时 ,我们把 G称为 n-准可扩的 .在这篇文章里 ,我们研究了 n-准可扩图的一些性质     

树的匹配覆盖

设图G没有孤立点.图G的匹配覆盖数,记为mc(G),是指满足如下条件的最小正整数k:G有k个匹配M1,M2,…,Mk覆盖图G的所有顶点.证明了如果图G是一个树,则mc(G)∈{Δ0(G),Δ0(G) 1},其中Δ0(G)是指使得图G的某个顶点有l个一度邻点的l的最大值.而且,任给一个树G,给出了一个可以确定图G的匹配覆盖数的线性算法.     

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

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

饱和二部图

没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X包含于V（G）,Γ（X）表示V（G）中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=（U,W）是饱和的当且仅当（a）存在唯一X包含于U,使得X〉Γ（X）,X-1〉Γ（X）且G的导出子图G[X∪Γ（X）]是完全二部图;（b）G的导出子图G[（U-X）∪（W-Γ（X））]是完全二部图,且满足U-X＋1=W-Γ（X）;（c）U-X中每个顶点与W中的每个顶点都相邻,且X∪（W-Γ（X））是图G的一个独立集.