论文部分内容阅读
在此论文中,主要介绍图中一定条件的不交团及独立的圈在一些二分图中的相关结果. 本文令G代表一个图,它的顶点集和边集分别用V(G)和E(G)来表示.设v∈V(G),则点v在G中的度数表示为dG(v),图G的最大度和最小度分别表示为△(G)和δ(G).定义σ2(G)=min{d(x)+d(y)|x,y∈V(G),xy(∈)E(G)}.称k个图是可填装的,如果它们可嵌入到一个完全图中使得其中任意两个是边不交的.若k=2则称为2-填装,图中点不交的子图问题是一类特殊的2-填装问题.G的一个完全子图被称为团,若一个团中包含的顶点数为k,那么称其为k-团.1963年,Erd(o)s提出了一个关于图中包含k个点不交团的猜想.令G是一个顶点数为n的图,满足n=sk,s和k为正整数且s≥3,k≥1.若δ(G)≥(s-1)k,则G含有k个点不交的Ks.当s=4时,1978年Bollobós证明了:令G是一个顶点数为n的图,其中n=4k,k为正整数.若满足δ(G)≥3n/4,那么G包含k个独立的4-团.最近,Wang证明了:假设δ(G)≥[n/2],那么G包含k个独立的圈,其中k-1个为4-圈.此文将4-圈推广到4-团,研究了图中具有特定性质的不交团问题,证明结果如下: 结果1:令G是一个顶点数为n的图.如果n≥4k,k为正整数.并且δ(G)≥3n/4,那么G包含k-1个独立的4-团和一个弦圈,弦圈上的度大于等于3. 对于二部图G=(V1,V2;E),令G的两个部分的顶点集合分别为V1和V2.若|V1|=|V2|,则称G为均衡二部图.定义δ1,1(G)=min[d(x)+d(y)|x∈V1,y∈V2}.δ2,2(G)=min{d(x)+d(y)+d(u)+d(v)|x,y∈V1;u,v∈V2}.和σ1,1(G)=min{d(x)+d(y)|x∈V1,y∈V2,xy(∈)E(G)}.σ2,2(G)=min{d(x)+d(y)+d(u)+d(v)|x,y∈V1;u,v∈V2,e({x,y},{u,v})=0}. 如果一条路(或一个圈)被称为G的哈密顿路(或哈密顿圈),则图G中存在一条路(或一个圈)包含图G的所有点.著名的哈密尔顿圈理论的广义推广之一是图中独立的圈的问题.在1952年,Dirac证明了定理:令G是一个顶点数为n≥3的图,假若δ(G)≥n/2,则G中有一个哈密尔顿圈.在1963年,Corrádi和Hajnal证明了假设G是一个顶点数为n≥3k的图并且满足最小度δ(G)≥2k,则G包含k个独立的圈.对于二部图,1996,Wang证明了:令二部图G=(V1,V2;E)满足|V1|=|V2|=n≥2k+1,若δ(G)≥k+1,则G包含k个独立的圈.Enomoto提出是否可以用δ1,1或者σ1,1代替定理中的δ.2009,Yan和Gao证明了用σ1,1代替δ的情况.本文用σ2,2代替δ,进一步研究均衡二部图中点不交圈的相关问题,得到如下结果: 结果2:令k,n为两个正整数,G=(V1,V2;E)为一个二部图且满足|V1|=|V2|=n≥4k+4.如果σ2,2(G)≥4k+4,那么G包含k个点不交的圈.