共查询到20条相似文献,搜索用时 78 毫秒
1.
设G=(V1,V2;E)是一个二分图,其顶点数目满足|V1|=|V2|=n≥(k+1)s+1,s和k是满足s≥3并且k≥1的两个正整数. 定义σ1,1为图G的属于不同分划中的不相邻顶点的最小度和,证明了如果σ1,1(G)≥2[(1-1/s)n]+2, 则G有一个2-因子包含至少k个圈,使得每个圈的长至少为2s. 相似文献
2.
该文主要证明了若G=(V1,V2:E)是一个满足|V1|=|V2|=n≥sk的二分图,其中k,s,n为3个正整数且k≥2,s≥4,如果σ1,1(G)σ2[(1-1/s)n+k],那么对G的任意k条独立边e1,…,ek,G有一个包含k个点不交的圈C1,…Ck的2-因子,使得ei∈E(Ci),且|Ci|≥2s. 相似文献
3.
该文主要证明了若G=(V1,V2;E)是一个满足|V1|=|V2|=n≥sk的二分图,其中k,s,n为3个正整数且k≥2,s≥4,如果σ1,1(G)≥2「(1-1/s)n k﹁,那么对G的任意k条独立边e1,…,ek,G有一个包含k个点不交的圈C1,…,Ck的2-因子,使得ei∈E(Ci),且|Ci|≥2s. 相似文献
4.
5.
与几类子图2-正交的(g,f)-因子分解 总被引:4,自引:1,他引:3
设g和f分别是定义在图G的顶点集合V(G)上的整数值函数且对每个x∈V(G)有g(x)≥2。本文证明了:若G是一个(mg+m-1,mf-m+1)-图,则对于G中任意给定的子图2K1,m或2m-星或2m-对集,G有一个(g,f)-因子分解与之2-正交。 相似文献
6.
设G=(V1,V2;E)是一个二分图, 其顶点数目满足V1=V2=n≥sk,s和k是满足s≥3并且k≥2的两个正整数. 如果σ1,1≥2「(1-1/s)n」+k, 那么G对的任意k个顶点v1,v2,…,vk,G有一个包含k个点不交圈G1,G2,…的因子,使得vi∈V(ci)且Ci≥2s. 相似文献
7.
设G是一个简单图,任意e∈E(G),定义e=uv在G中的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。 相似文献
8.
二分图中相互独立的圈 总被引:1,自引:0,他引:1
颜谨 《山东大学学报(理学版)》2002,37(5):396-400,403
证明了下面的结论:设k≥1是一个整数,G=(V1,V2;E)是一个二分图,满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1,y∈V2,都有d(x) d(y)≥2k 2,并且δ(G)≥2,则G包含k个相互独立的图。 相似文献
9.
与任意图2-正交的(g,f)-因子分解 总被引:4,自引:0,他引:4
设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g(x)和f(x)是定义在V(G)上的两个整数值函数,且对每个x∈V(G),有4≤g(x)≤f(x),则图G的一个支撑子图F称为G的一个(g,f)-因子,如果对每个x∈V(G),有g(x)≤dF(x)≤f(x)。图G的(g,f)-因子分解是指E(G)能划分成边不交的(g,f)-因子,设F={F1,F2,…,Fm}和H分别是图G的因子分解和子图,若对所有1≤i≤m有|E(H)∩E(Fi)|=2,则称F和H2-正交。本文证明:若G是一个(mg m-1,mf-m 1)-图,H是G中任一有2m条边的子图,则G有一个(g,f)-因子分解与H2-正交。 相似文献
10.
给出了一个二分图G =(V1 ,V2 ;E)有一个支撑子图包含一个指定长度的圈和一个对集的度条件 .并且证明了若 |V1 |=|V2 |=n =2k ,则G有一个 2 因子恰有一个 8 圈和k 2个 4 圈或恰有k个 4 圈 . 相似文献
11.
Guo Liren 《广西师范学院学报(自然科学版)》1998,(2)
设G是连通偶图,(X1,X2)是其顶点的二分类,|X1|=|X2|=n,δ(G)≥t≥3。证明了若任意u,v∈Xi蕴含|N(u)∪N(v)|≥n-(t-2),i=1,2,则当t=7时G是点泛圈偶图。 相似文献
12.
13.
曾永宁 《重庆大学学报(自然科学版)》1989,12(2):43-49
本文针对一类特殊的多关系查询——偶查询,提出了一种建立在图论偶图和匹配理论基础上的查询优化方法,这种方法具有多项式复杂性。 相似文献
14.
本文应用 De Bruijn 的幂群计数定理和偶图计数结果,解决了偶自补图的计数问题,获得了 m 个顶点独立集与 n 个顶点独立集的所有偶自补图的数目:当 m≠n 时是a_(mn)~C=Z(S_m×S_n;0,2、0,2,…),当 m=n 时是a_(mn)~C=Z([S_n]~S_2;0,2,0,2,…).文中并给出了计数偶自补图数目的实用公式. 相似文献
15.
图的染色理论是图论的一个重要分支。本文使用分析的方法得到了轮和完全等二部图联图的全色数、均匀全色数和邻点可区别边色数。 相似文献
16.
作者给出了二部图是λ4-最优的和超级-λ4的范型条件,而且给出例子说明其独立性.这些结果在网络可靠性分析中有一定应用. 相似文献
17.
党恺谦 《辽宁师范大学学报(自然科学版)》1993,16(4):275-279
设G(A,A2;E)为2连通偶图,(A1,A2)为顶点二分划,D(x)={y|y∈V(G)\{x},d(x,y)=2},d^*d(x)表示D(x)∪{x}中所有的度排成的非减度序列(d^*1,d^*2,…,d^*j,…,d^*|D(x)|+1)中当下标j=d(x)时的度而当|D(x)|+1<d(x)时d^*d(x)=d^*|D(x)|+1。δ0=min{d(x)|x∈V(G)},δi=min{d^ 相似文献
18.
二分图中k-因子存在的两个充分条件 总被引:1,自引:0,他引:1
钱建波 《山东大学学报(理学版)》2001,36(4):477-480
设G=(X,Y;E)为二分图,其中|
X |=| Y |=n为整数.证明了若 相似文献
19.
文中证明了2-连通平衡二部图中Hamilton圈存在性的一个Fan一型充分条件 相似文献
20.