分数(g,f,n)-临界图的韧度条件的改进

讨论了分数(g,f,n)-临界图与韧度之间的关系,对于满足条件1≤a≤b和b≥(1+√(4n+5))/2的正整数a,b,n,证明了当图的韧度满足t(G)≥(b-1)(b+n+1)/a时,图G是分数(g,f,n)-临界图。     

关于在K1,n-free图中存在正则因子度条件的推广

图被称为K1,n-free图,如果它不含有导出子图K1,n。设G是一个具有顶点集V(G)的图,并设g和f是两个定义在V(G)的函数,使得g(x) f(x)对所有V(G)中的点x都成立。设a=max{g(x)|x∈V(G)},b=min{f(x)|x∈V(G)},并有b,a 2,n b/(a-1) 1(如果存在点v∈V(G)使得f(v)≡1(mod2),假定b n-1)。证明了:每个连通的使得∑x∈V(G)f(x)为偶数的K1,n-free图G有(g,f)-因子,如果它的最小度至少是(n-1)(a 1)b 1「b a(n-1)2(n-1) -n-1b「b a(n-1)2(n-1) 2 n-3.这个结果是K.Ota和T.Tokuda(J.GraphTheory.1996,22:59-64.)关于在K1,n-free图中存在正则因子度条件的推广。     

图的孤立韧度与分数(g,f)-因子的存在性

讨论了孤立韧度与图的分数(g,f)-因子的存在性的关系,证明了当a≡b(mod2)且δ(G)和I(G)都不小于(a+b)2+2(b-a)4a,或者当a b(mod2),δ(G)和I(G)都不小于(a+b)2+42a(b-a)+1时,图G有分数(g,f)-因子。     

有1-因子的图和(g,f)-对等图

既是(g,f)-覆盖又是(g,f)-消去的图称为(g,f)-对等图.给出了有1-因子F的图是(g,f)-对等图、f-对等图的关于F的分支的若干充分条件,证明了如下定理:设G是一个图,F为G的1-因子,w(F)≥2且w(F)≡0(mod 2);g和f是定义在V(G)上的整数值函数并且对每个x∈V(G)都有g(x)≤f(x).若对F的每个分支C=xy,G-{x,y}是(g,f)-对等图,则G也是(g,f)-对等图.并指出定理中的条件在一定意义上是最好可能的.     

图有不含匹配的[a,b]-因子的邻域条件

设G是一个n阶图,a和b是整数使得1≤a＜b.设H是G的具有m条边的匹配,δ(G)是最小度.证明了若δ(G)≥a+1,n≥2(a+b)(a+b-1)/b,并且对G的任意两个不相邻的点x和y都有|NG(x)U NG(y)|≥an/(a+b)+2,则G有[a,b]-因子F使得E(H)nE(F)=     

双环网的宽直径

宽直径是度量网络通信延迟和容错性能的重要指标,而环网是局域网中广泛应用的一种网络结构。根据环网的对称性和点传递性,用点不交的最短路径算法研究了一类双环网C(n;a,b)(其中a,b是n的非平凡因子且a,b互素)的k-宽直径,并得到如下结论:当n=ab时,d₄(C(n;a,b))≤La／2」+b-1;当n=2ab时,d₄(C(n;a,b))≤a+b-1;当n=abr,r>2时,d₄(C(n;a,b))≤(r-1)a+b-2。     

(f，g)-反演的数学归纳法证明

马欣荣建立了最广泛的一对矩阵反演(f,g)-反演,它取决于所给的一对函数f(x,y)、g(x,y),对Aa,b,c,是否满足方程g(a,b)f(x,c)-g(a,c)f(x,b) g(b,c)f(x,a)=0,并给出了该反演的算子法证明.文章就(f,g)-反演给出了较简单、易于理解的数学归纳法证明.     

二分图中度条件与[a,b]-覆盖图

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g相似文献   

二分图上有限制条件的(g,f)-因子和f-因子

设图G=(X,Y,E)是二分图,g,f是定义在V(G)上的正整值函数,且对任意的x∈V(G)有g(x)＜f(x),证明了:如果图G是(mg,mf-1)-图,M是G的任一含有m条边的对集,则存在图G的一个(g,f)-因子F,使F包含M任意给定的一条边,并且不包含其他的m-1条边;二分图G是(2m-1)-边连通的(mf)-图,则图G有一个f-因子包含任意给定的一条边,并且不包含任意其他的m-1条边.     

关于分数(g,f)-2-覆盖图

设G是一个图,并设h是定义在图G的边集E(G)上的一个函数,使对任意的e∈E(G),有h(e)∈[0,1]。令dhG(x)= x瘕?h(e),则称dhG(x)是G中顶点x的分数度。若h满足对任意的x∈V(G),有g(x)≤dhG(x)≤f(x),则称h是G的一个分数(g,f)-因子。一个图称为分数(g,f)-2-覆盖图,如果对图G中的任何两条边e1和e2,G都有一个分数(g,f)-因子h满足h(e1)=1和h(e2)。本文给出了一个图是分数(g,f) 2 覆盖图的充分必要条件。     

二分图上有限制条件的(g,f)-因子分解

设G=(X,Y,E)是二分图,g,f是定义在V(G)上的正整数值函数,且对任意的x∈V(G)有g(x)＜f(x).令G是(mg,mf-1)-图,证明了:①若,g(x)≥1,H是G的任一含有m条边的子图.则G有一个(g,,)-因子分解与H-正交.②若g(x)≥2,H是G的任一含有2m条边的子图,则G有一个(g,f)-因子分解与H2-正交.     

二分图上有限制条件的(g,f) 因子和f 因子

设图G=(X,Y,E)是二分图, g,f是定义在V(G)上的正整值函数, 且对任意的x∈V(G)有g(x)＜f(x), 证明了: 如果图G是(mg,mf-1)-图, M是G的任一含有m条边的对集, 则存在图G的一个(g,f)-因子F, 使F包含M任意给定的一条边, 并且不包含其他的m-1条边; 二分图G是(2m-1)-边连通的(mf)-图, 则图G有一个f-因子包含任意给定的一条边, 并且不包含任意其他的m-1条边.     

图存在分数［a,b］-因子的一个孤立韧度条件

给出了图的孤立韧度I(G)与分数［a,b］-因子存在性间的关系,证明了若δ(G)≥I(G)≥a-1+(a-1)／b,其中a、b均为整数,2≤a＜b,则图G有分数［a,b］-因子。进一步证明该结论在一定意义下是最好的,并且提出猜想当a=b时结论仍然成立。     

（g，f，k）临界图的一个充分必要条件

设G是-个简单图,g和f是两个定义在V（G）上的整数值函数,且对所有的x∈V（G）都满足g（x）≤f（X）．如果删除G的任何k个顶点后,图G的其余部分含有-个（g,f）因子,那么称图G为一个（g,f,k）-临界图．本文给出了-个图是（g,f,k）-临界图的-个充要条件,并对这些奈件的应用作了讨论。进-步,本文研究了（g,f,k）-临界图的性质．