一个匹配是导出匹配的条件

称图G的一个匹配M是导出的，如果M是由M所覆盖的顶点导出的子图的边集，分别给出二部图的一个匹配是导匹配的条件及存在一个最大匹配是导出匹配的条件。     

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

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

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

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

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

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

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

研究直径为2的无爪图的导出匹配可扩性,得出结论:直径为2的无爪图G是导出匹配可扩的,当且仅当对图G的任意的导出匹配M,|M|≤3,G-V(M)没有奇分支,从而,直径为2的无爪图的导出匹配可扩性是多项式时间可解的.     

具有度序列(4~1,2~(p-1))图的匹配唯一性

设G是一个简单图,M（G;W）是由Farrell引进的G的匹配多项式,若对任何图H,M（G;W）=M（H;W）导出G同构于H,则称G是匹配唯一的。Farrell和Guo首先研究了圈和道路的匹配唯一性问题。本文研究具有度序列（4~1,2~（p-1））的图的匹配唯一性,得到了若干匹配唯一的图类。     

拟轮图的导出匹配可扩性

从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.     

关于偶匹配可扩图中删去两个点(英文)

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

树的匹配覆盖

设图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的匹配覆盖数的线性算法.     

结合图的导出匹配可扩性

简单图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是有完美匹配的简单连通图．称图G是偶匹配可扩的，是指G的每一个偶匹配都可以扩充成为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-偶匹配可扩性的.     

步长为1和n/2循环图的导出匹配可扩性研究

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±n2(mod2n)的i和j,均有xixj∈E(G),则称其为步长为1和n2的循环图,记为C2n(1,2n).本文的主要结论为:C2n(1,2n),n#4,是导出匹配可扩的.     

直径是2的图的导出匹配可扩性

研究直径是2的图和直径是3的树的生成母图的导出匹配可扩性; 给出了一类导出匹配可扩的拟轮图, 并研究了直径是3的树加边的导出匹配可扩性.     

循环图中部分图类的导出匹配可扩性

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G,)则称其为步长为1和k的循环图,记为C2n(1,k.)通过详细讨论循环图的导出匹配可扩性,具体给出了循环图中的部分图类的导出匹配可扩性。     

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

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