首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
与星正交的(g,f)-因子分解   总被引:1,自引:0,他引:1       下载免费PDF全文
刘桂真 《中国科学A辑》1995,38(4):367-373
设g和f分别是定义在图G的顶点集合V(G)上的整数值函数且对每个x∈V(G)有0≤g(x)≤f(x),证明了若G是一个(mg+m-1,mf-m+1)-图,则对G中任意一个给定的有m条边的星H,G有一个(g,f)-因子分解与H正交.  相似文献   

2.
具有正交的(g,f)-因子分解的子图   总被引:3,自引:0,他引:3       下载免费PDF全文
闫桂英 《中国科学A辑》1997,40(11):961-961
仅考虑简单图.设G是一个图,g(x)和f(x)是定义在V(G)上的整数值函数,且对任意的x∈V(G),设g(x)≤f(x),H是G的一个子图,F={F1,F2,…,Ft}是G的一个因子分解,如果对所有的1≤i≤t, |E(G)∩E(Fi)|=1,则称F与H正交.证明了:设G是一个(mg(x)+k,mf(x)-k)-图,其中对任意的x∈V(G),g(x)≥1或f(x)≥5是定义在V(G)上的整数值函数,1≤k<m,则存在一个子图R满足对G的任意子图H,|E(H)|=k,R有(g,f)-因子分解与H正交.  相似文献   

3.
图中具有正交(g,f)因子分解的子图   总被引:1,自引:0,他引:1  
设G是一个 (mg +k ,mf -k) -图 (1≤k 相似文献   

4.
李国君  刘桂真 《数学学报》2003,46(4):715-728
设G是一个图,具有顶点集合V(G)和边集合E(G).设g和f是定义在V(G)上的整数值函数,使对每个x∈V(G),有g(x)≤f(x).图G的一个(g,f)-因子是G的一个支撑子图H,使对每个x∈V(G),有g(x)≤d_H(x)≤f(x).G的一个(g,f)-因子分解是E(G)的边不相交的(g,g)-因子的一个划分.设F={F-1,F_2,…,F_m}为G的一个因子分解,H是G的一个有mr条边的子图.如果每个F_i恰好与H有r条公共边,1≤i≤m,则称Fr-正交于H.本文证明每个(mg+kr,mf-kr)-图含有一个子图R,使R有(g,f)-因子分解r-正交于任意给定的有kr条边的子图,其中m,k和r为正整数且k相似文献   

5.
关于图中子图的(n,k)—正交因子分解   总被引:1,自引:0,他引:1  
李建湘 《数学研究》2001,34(4):339-344
设G是一个具有顶点集V(G)和边集E(G)的图. 设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H.  相似文献   

6.
设m,k和r为正整数,且使l≤k<m.设G是一个具有顶点集合V(G)和边集合E(G)的图,并设g和f是定义在V(G)上的使对每个x∈V(G)有r≤g(x)≤f(x)的整数值函数.设H1,H2,…,Hr是G的r个顶点不相交的子图且|E(Hi)|=k,1≤i≤r.本文证明了每个(mg+k,mf-k)-图有k个边不相交的(g,f)-因子正交于Hi,1≤i≤r.  相似文献   

7.
G是一个图,g和f是两个定义在V(G)上的非负整数值函数,并且对任意的x∈V(G),满足g(x)≤f(x).称图G是分数(g,f,m)-覆盖图,如果存在图G的分数(g,f)-因子G[F_h]满足对任意的e∈E(H)有h(e)=1,其中H是图G的m条边的子图.证明了一个图是分数(g,f,m)-覆盖图的充要条件,并得到了几个推论.  相似文献   

8.
设G是一个图,并设g和f是定义在V(G)上的整值函数使得对所有的点x∈ V(G)均有g(x)≤ f(x).称一个图G是(g,f,H) -可扩的,如果在删除了任意一个同构于H的子图中所有点后,剩下G的子图有一个(g,f) -因子.该文给出了(g,f,H) -可扩图的特征.进一步,研究了(g,f,H) -可扩(H=nK1)的性质.  相似文献   

9.
肖岚  刘岩 《运筹学学报》2012,16(3):132-138
设G是一个简单图, f是定义在V(G)上的整数值函数,且m是大于等于2的整数. 讨论(0, mf-k+1)-图G的正交因子分解, 并且证明了对任意的1≤k≤m, (0, mf-k+1)-图G中存在着一个子图R, 使得R有一个(0,f)-因子分解正交于图G中的任意一个k-子图H.  相似文献   

10.
设G是一个图,具有顶点集V(G)和边集E(G).设g和f是定义在V(G)上的整数值函数且对每个x∈y(G)有g(x)≤f(x).本文证明了如下的结果:若G是一个(mg+kr,mf-kr)一图,且对每个x∈V(G)有g(x)≥r-1,H和G的任意给定的有kr条边的子图,则G中含有一个子图R,使R有(g,f)-因子分解r-正交于H,其中m,k和r是正整数且k〈m.  相似文献   

11.
周思中  薛秀谦 《数学研究》2004,37(4):417-420
设 G是一个图 ,用 V(G)和 E(G)表示它的顶点集和边集 ,并设 g和 f是定义在 V(G)上的两个整数值函数且 g 相似文献   

12.
设G是一个图. 设g和f是两个定义在V(G)上的整值函数使得对V(G)所有的顶点x有g(x)f(x). 图G被称为(g,f,n)-临界图,如果删去G的任意n个顶点后的子图都含有G的(g,f)-因子. 本文给出了图是(a,b,n)-临界图几个充分条件. 进一步指出这些条件是最佳的. 例如,如果对V(G)所有的顶点x和y都有g(x)<f(x), n+g(x)dG(x)和g(x)/(dG(x)-n)f(y)/dG(y),则G是(g,f,n)-临界图.  相似文献   

13.
§1.定义和记号 本文中所考虑的图是可以有重边际没有环的图,G是一个图,g,f是定义在V(G)上的整数值函数,对∈V(G),满足g(x)≤f(x),H是G的一个支撑子图且满足g(x)≤d_H(x)≤f(x),∈V(G),则称H是G的一个(g,f)一因子。  相似文献   

14.
禹继国  刘桂真 《应用数学》2003,16(1):126-129
设G是一个二分图具有顶点集V(G)和边集E(G)。设g和f是定义在V(G)上的两个正整值函数使对任意的x∈V(G)有g(x)≤f(x),G的一个(g,f)-因子H是G的一个生成子图满足g(x)≤dH(x)≤f(x)。若图G本身是一个(g,f)-因子,则称G是一个(g,f)-图。本文得到一个(mg,mf)-图具有特殊性质的(g,f)-因子的充分条件,从而推广了文献[6]中的一个结果。  相似文献   

15.
消去图、覆盖图和均匀图的若干结果   总被引:2,自引:0,他引:2  
设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

16.
设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g<f.图G的一个(g,f)-因子是G的一个支撑子图F使对任意的x∈V(G)有g(x)≤dF(x)≤f(x).如果过图G的任意k条边都有一个(g,f)-因子,则称图G是一个(g,f)-k-覆盖图.如果图G的任意k条边不属于它的一个(g,f)-因子,则称图G是一个(g,f)-k-消去图.作者分别给出了一个图是(g,f)-k-覆盖图和(g,f)-k-消去图的充分条件.  相似文献   

17.
设G=(X,Y,E(G))是一个二分图,分别用V(G)=XUY和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对(A)x∈V(G)有f(x)≥k.设H_1,H_2,…,H_k是G的k个顶点不相交的子图,且|E(H_i)|=m,1≤i≤k.本文证明了每个二分(0,mf-m+1)-图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k).  相似文献   

18.
图的1-因子、f-因子和(g,f)-因子   总被引:5,自引:0,他引:5  
设G是一个图且有一个1-因子F,g和f是定义在V(G)上的非负整数值函数且对每个X∈V(G)有g(X)<f(X)≤dG(x),且f(v(G))为偶数.(i)若对每个xy∈F有f(x)=f(y)且G-{x,y}有一个(g,f)-因子,则G有一个(g,f)-因子;(ii)若对每个xy∈F有f(X)=f(y)且G-{X,y}有f-因子,则G有f-因子.  相似文献   

19.
设G是一个图,g和f是定义在V(G)上的一整值函数且满足对于所有x∈V(G)均有g(x)≤f(x)以及g(x)≡f(x)(mod2)。称G的生成子图F为一个(g,g 2,…,f)-因子,如果对于一切x∈V(G)有degF(x)∈{g(x),g(x) 2,…,f(x)},当g(x)=1时(对于所有x∈V(G),这样的因子称为(1,f)-奇因子。本文给出了一个图G具有(g,g 2,…,f)-因子和包含G中任意给定一条边的(1,f)-因子的充要条件,并据此,得到了一些有趣的结果。  相似文献   

20.
一个图称为分数(g,f,m)-消去图若删除任意m条边后的剩余子图依然存在分数(g,f)-因子.本文证明若图G的阶为n,1≤a≤g(x)≤f(x)-Δ≤b-Δ对任意顶点x∈V(G)成立,δ(G)≥(b-Δ)(b+1)/a+2m,n≥(a+b)(2(a+b)+2m-1)/(a+Δ),且|N_G(x_1)∪N_G(x_2)|≥(b-Δ)n/(a+b),对任意不相邻顶点x_1和x_2都成立,则G是分数(g,f,m)-消去图.这个领域并条件在一定程度上是最好的.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号