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

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

硼氮富勒烯图的反强迫数

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

一类乘积图的Pfaffian性

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

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

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

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

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

关于n-可扩图的一些新充分条件

若图G包含一个经过G的每个顶点的圈,则称图G为Hamilton图.若一个连通图G有n条独立边,且任意n条独立边都可扩展为G的完美匹配,则称G为n-可扩图.利用判别Hamilton图的Fan-型条件和Chvatal-Erdos型条件,分别得到两个新的判别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的匹配覆盖数的线性算法.     

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

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

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

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

饱和二部图

没有完美匹配的二部图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的一个独立集.     

饱和二部图

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

循环图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-偶匹配可扩性的.     

3元立方体的匹配排除

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

平面二部图的完美匹配集合上的有向根树结构及其生成

图的完善匹配或１－因子指覆盖子其所有顶点的独立边集。对含有完善匹配的平面二部图，其所有完美区通过某旋转变换形成层次组织结构。可用有向根树或半格表示。建立了平面二部图的完善匹配集合上新有向根树结构并可通过算法来生成。     

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

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

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

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

可扩图的一些性质

设G是一个连通的简单图且具有完美匹配。如果G的任一基数为n(n≤(|V(G)|-2)/2的匹配都能扩充为G的一个完美匹配，则称G为n-可扩的。对于S包含于V(G),记M是G[S]的基数为r的最大匹配，并令T＝S－V（M）。对连通的非二部的n-可扩图G（n≥2），得到以下结果：（1）若r≤n且|T|≥2，则|V(G)|≥2(n r |T|--1)。（2）若r≤n-2且|T|≥2，则|V(G)|≥2(n r |T|)。（3）若|V(G)|≤4n-2，则对于任一u∈V(G),G[Г(u)]都有一个基数为n的匹配。     

结合图的导出匹配可扩性

简单图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中一个有完美匹配,另一个有几乎完美匹配.     

k-正则图的可扩性质

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

n棱柱的完美匹配计数及其k-共振性

当n≥3时,笛卡尔积图C_n×P₂是一个多面体图,也称为n棱柱,其中C_n为n长圈,P₂为2长路。令G是一个n棱柱的平面嵌入图,k是正整数,若对任意的正整数i(0≤i≤k),从图G中任意删除掉i个两两不交的偶面所得到的图有完美匹配,则称图G是k-共振的。首先得到n棱柱完美匹配数的计算公式;然后对n棱柱的共振性进行讨论,得到了n棱柱是1-共振、2-共振的和k-共振的(k≥3)。