论文部分内容阅读
本文所考虑的图都是简单无向图.设G=(V(G),E(G))是一个图,其中V(G)和E(G)分别表示G的顶点集合和边集合.顶点x在G中的度记为dG(x),δ(G)表示G中所有顶点度的最小值.对于任意的集合S(¢)V(G),由S导出的G的子图记为G[S],G-S表示由V(G)\S导出的子图.用o(G-S)和i(G-S)分别代表G-S中奇分支的个数和孤立顶点的个数.
设g(x)≤f(x)是定义在V(G)上的两个非负整数值函数,H是G的一个支撑子图.如果对于任意的x∈V(G),满足g(x)≤dH(x)≤f(x),则称H是G的一个(g,f)-因子.类似的,如果对于任意的x∈V(G),满足g(x)=f(x),则称日是G的一个f-因子(或g-因子);如果对于任意的x∈V(G),有g(x)=a,f(x)=6且a,b是两个正整数,那么(g,f)-因子就可被称为[a,b]-因子.特别的,对于任意的x∈V(G),有g(x)=f(x)=1时,(g,f)-因子就变成了1-因子,即完美匹配.
设g(x)≤(x)是定义在V(G)上的两个非负整数值函数,h(e)∈[0,1]是-个定义在E(G)上的函数并且dhG(x)=∑e∈Exh(e),其中Ex={xy:xy∈E(G)}.此时dhG(x)被称为是在h作用下的G中顶点x的分数度,h被称为是一个指示函数(inditor fullction).如果对于任意的x∈V(G),有g(x)≤dhG(x)≤f(x),设Eh={e:e∈E(G),h(e)≠0}且Gh是G的一个支撑子图并使得E(Gh)=Eh,那么Gh就是G的一个分数-(g,f)-因子.同样的方法可以类似的定义分数-k-因子、分数-[a,b]-因子等.特别的,对于任意的x∈V(G),有g(x)=f(x)=1时,分数-(g,f)-因子变为分数-1-因子,即分数完美匹配.
图的因子理论是图论中研究的主要问题之一.对因子理论的研究在一个多世纪以前就开始了,但直到上世纪七十年代才逐渐地活跃了起来.到目前为止,对图的因子方面的研究已经得到了不少成果.分数图论是相对年轻的分支,因此仍有许多问题有待解决.
本文共分为六大部分,第四部分和第五部分是整个文章的核心,通过分析证明得出了分数因子临界图和分数-(r,k)-可扩图的一些结论.
第一部分是全文的基础部分.简要介绍了文中所涉及的概念、术语和符号,回顾了图论及图因子问题的发展史,并对图因子问题中常用的重要参数作了详细介绍.
第二部分概括总结了图因子存在性问题中整数因子和分数因子已有的重要定理.
第三部分分析概括出图因子存在性问题中的两种常用研究方法.
第四部分重点研究了分数因子临界图(设G是一个图,若对于顶点集合V(G)的任意n-子集T使得G-T有分数-r-因子,则称G是-个分数-(r,n)-因子-临界图)的一些性质,得出了以下结论:
设G是δ(G)≥r+n的图且孤立韧度I(G)≥r+n-1/r.则G是一个分数-(r,n)-因子-临界图.
假设G是δ(G)≥r+n的图.若G是分数-(r,n)-因子-临界图,则G也是分数-(r,n-1)-因子-临界图.
如果对于任意的u∈V(G),G-{u}-有分数-r-因子,那么G同样也有分数-r-因子.第五部分主要研究了分数-(r,k)-可扩图(设G是一个图,如果对于V(G)的任意r-子集T,G-T是一个分数-k-可扩图,则G是一个分数-(r,k)-可扩图)的一些性质,得出了以下结论:
图G是一个分数-(r,k)-可扩图当且仅当对于任意的集合U∈V(G),有i(G-U)≤U-2K-r.其中,|U|≥2k+r且G[U]包含一个k-匹配.
任意—个分数-(r,k)-可扩图同时也是—个分数一(r1,k1,)-可扩图,其中0≤r1≤r,0≤k1≤k.
设G是—个图.则G是—个分数-(r,k).可扩图当且仅当对于G任意的一个i-匹配M(0≤i≤k),G-V(M)是一个分数-(r,k-i)-可扩图.
一个分数-(r,k)-可扩图是分数-(k+r/2)-可扩的.
第六部分是对全文的一个总结以及对下一步工作的展望.