Harary图的k-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等.

步长为1和4的循环图的k-偶匹配可扩性

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配。判定图是否含有基数为k的偶匹配是NP-困难问题,该文主要刻画了循环图C_(2n)(1,4)的k-偶匹配可扩性。

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

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

关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G,如果对于V(G)的任意k元子集S,子图G-S都包含分数完美匹配,那么称G为分数后-因子临界图.如果图G的每个k-匹配M都包含在一个分数完美匹配中,那么称图G为分数k-可扩图.给出一个图是分数k-因子临界图和分数k-可扩图的充分条件,并给出一个图是分数k-因子临界图的充分必要条件.

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

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

文章主要刻画了循环图C2n(1,2n/3)的k-偶匹配可扩性,得出对任意的n(n>3),C2n(1,2n/3)是2-偶匹配可扩性的。

几类特殊图的匹配可扩性

如果图G的每一个偶匹配都可以扩充为G的一个完美匹配,则称图G是偶匹配可扩的。论文主要刻画了图Cm×Pn、Pm×Pn和双轮图的匹配可扩性,从而为研究这些图的可扩性奠定了基础。

曲面可扩性的一个注解(英文)

推广了Aldred,Kawarabayashi and Plummer关于曲面上图的可扩性的结果.证明了,如果|V(G)|>8g(G)-8/k-3或|V(G)|>4g(G)-8/k-3(k≥4),那么G不是k-可扩的,其中g(G)和g珘(G)分别是G可定向亏格及不可定向亏格.

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

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

n-正则(n-2)-边可删的导出匹配可扩图

设图G是有2n个顶点的简单图,如果对于E(G)的任一满足|F|=k的子集F,G-F均为导出匹配可扩的,则称图G是k-边可删的导出匹配可扩图.证明了n-正则(n-2)-边可删的导出匹配可扩图只有Kn,n,其中n≠4k,k≥3.

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

称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(|V(G)|-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.根据循环图的性质研究了图C_(2n)(1,(2n+1)/3)的匹配可扩性,证明了对于任意的n(n≥4),C_(2n)(1,(2n+1)/3)是3-偶匹配可扩的.