关于2k可删的及k边可删的导出匹配可扩图的一些结果

论文摘要

本文涉及的图均为有限,非空,无向,简单图。本文主要研究下列四方面的问题: 1.2k点可删的导出匹配可扩图的度条件。 2.k边可删的导出匹配可扩图的度条件。 3.3正则1边可删的导出匹配可扩图的刻划。 4.4正则、不包含K1,4作为导出子图、1边可删的导出匹配可扩图的刻划。 原晋江[33]提出了导出匹配可扩图问题。如果图G的每一个导出匹配都包含在图G的一个完美匹配中,我们则称图G是导出匹配可扩图,导出匹配可扩性问题已经吸引了很多图论学者致力于它的理论研究。关于导出匹配可扩图的研究结果,我们可以在[14]、[25]、[26]、[27]、[28]、[29]、[30]、[31]、[32]、[33]、[34]、[35]、[36]、[41]、[42]看到。为了进一步研究导出匹配可扩图的运算性质,我们提出了k边可删的导出匹配可扩图及2k点可删的导出匹配可扩图的概念:设图G是有2n个顶点的简单图,如果对于E（G）的任一满足|F|=k的子集F,G-F均为导出匹配可扩的,则称图G是k边可删的导出匹配可扩图;若对于V（G）的每一个满足|S|=2k的子集S,G-S均为导出匹配可扩图,则称图G是2k点可删的导出匹配可扩图。设G是有2n个顶点、具有二部划分（A,B）的二部图。如果对于V（G）的每一个满足|A∩S|=|B∩S|=k的子集S,G-S均为导出匹配可扩的,则称二部图G是2k点可删的导出匹配可扩图。受导出匹配可扩图的结果的启发,我们得出了一些关于2k点可删的导出匹配可扩图及k边可删的导出匹配可扩图的结果。 定理1 设图G是有2n个顶点的连通图。如果δ（G）≥（4n+2k-1）/3,则图G是2k点可删的导出匹配可扩图,其中n≥3,k≤n-1。 定理2 设图G是有2n个顶点的连通图,则「（4n+2k-1）/3」是最小的正整数δ,使得对于每一个δ（G）≥δ的图G均为2k点可删的导出匹配可扩图,其中n≥3,且k≤n-1。 定理3 设图G是具有二部划分（A,B）的二部图,如果δ（G）≥（2n+k+1）/3,则图G是2k点可删的导出匹配可扩图,其中|A|=|B|=n,k≤n-1。 定理4 设图G是有二部划分（A,B）的二部图,且|A|=|B|=n,则「（2n+k+1）/3」是

论文目录

• 1.引言
• 1.1.匹配理论简介
• 1.2.概念与术语
• 1.3.关于完美匹配与导出匹配可扩图的已知结果
• 1.4.本文的主要结果
• 2.2k点可删的导出匹配可扩图的度条件
• 2.1 2k点可删的导出匹配可扩图的度条件
• 2.2.2k点可删的导出匹配可扩二部图的度条件
• 3.k边可删的导出匹配可扩图的度条件
• 3.1.k边可删的导出匹配可扩图的度条件
• 3.2 k边可删的导出匹配可扩图的性质
• 4.3正则1边可删的导出匹配可扩图的刻划
• 1，4作为导出子图、1边可删的导出匹配可扩图的刻划'>5.4正则、不包含K_1，4作为导出子图、1边可删的导出匹配可扩图的刻划
• 6.参考文献
• 7.后记
• 8.致谢