首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到15条相似文献,搜索用时 62 毫秒
1.
若图的因子F的每一个分支都是完全图,则称F为完全-因子.本文研究了完全-因子F和(g,f)-对等图之间的关系,给出了有完全-因子F的图是(g,f)-对等图、f-对等图及k-对等图的关于F的分支的若干充分条件,并指出定理中的条件在一定意义上是最可能的,从而推广了李建湘等人的有关结果.  相似文献   

2.
关于分数(g,f)-因子消去图   总被引:10,自引:0,他引:10  
一个图称为分数(g,f)-因子消去图,如果去掉图G中的任何一条边e图G仍有一个分数(g,f)-因子。本文分别给出了一个力是分数1-因子消去图和分数2-因子消去图的几个充分条件,并给出一个图有一个分数(g,f)-因子不含给定对集中任何一条边的充要条件。  相似文献   

3.
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)-覆盖图的充要条件,并得到了几个推论.  相似文献   

4.
分数(g,f)-因子覆盖图   总被引:7,自引:0,他引:7  
一个图称为分烽(g,f)- 因子覆盖图,如果G中的任何一条边e都包含在一个分数(g,f)- 因子中,并且满足h(e)=1,其中h是分数(g,f)- 因子的导出函数。本文给出了一个图是分数(g,f)- 因子覆盖图的充要条件。  相似文献   

5.
李建湘 《应用数学》2004,17(3):450-455
设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 .  相似文献   

6.
设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)的性质.  相似文献   

7.
图的分数(g,f)-因子   总被引:19,自引:0,他引:19  
本文研究了图的分数因子的性质,特别给出了图的弧立韧度这一新概念,研究了孤立韧度与分数因子的关系,文中给出了一个图具有某些约束条件的(g,f)-分数因子的一些充分条件,得到了若干新结果,并提出 了一些可供进一步研究的问题。  相似文献   

8.
本文首先给出了(g,f)-3-覆盖图的定义,即一个图G称为(g,f)-3-覆盖图,如果G的任何三条边都属于它的一个(g,f)-因子;其次,黄光鑫曾先后给出了当g<f时一个二部图分别是(g,f)-2-覆盖图和(g,f)-3-覆盖图的充分必要条件,在此基础上,本文进一步得到了,当g≤f时一个二部图G=(X,Y)是(g,f)-3-覆盖图的一个充分必要条件;最后,研究了f(X)=f(Y)的情形,得到了当f(X)=f(Y)时一个二部图G=(X,Y)是f-3-覆盖图的一个充分必要条件.  相似文献   

9.
李国君  刘桂真 《数学学报》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相似文献   

10.
分数k-因子临界图的条件   总被引:1,自引:0,他引:1  
李巧  刘岩 《运筹学杂志》2013,(4):123-130
设G是-个连通简单无向图,如果删去G的任意k个项点后的图有分数完美匹配,则称G是分数k-因子临界图.给出了G是分数k-因子临界图的韧度充分条件与度和充分条件,这些条件中的界是可达的,并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件.  相似文献   

11.
令G=(V(G),E(G))是一个图,并令9和f是两个定义在V(G)上的整数值函数且对所有的x∈V(G)有g(x)≤f(z)成立.若对G的每一条边e都存在G的一个分数(g,f)-因子G_h使得h(e)=0,其中h是G_h的示性函数,则称G是一个分数(g,f)-消去图,若在G中删去E′■E(G),|E′|=k后,所得图有分数完美匹配,则称G是分数k-边-可消去的。本文给出了图是1-可消去,2-可消去和k-边-可消去的与韧度和孤立韧度相关的充分条件。证明了这些结果在一定意义上是最好可能的.  相似文献   

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.
On (g, f)-Uniform Graphs   总被引:3,自引:0,他引:3  
A graph G is called a (g, f)-uniform graph if for each edge of G, there is a (g, f)-factor containing it and another (g, f)-factor excluding it. In this paper a necessary and sufficient condition for a graph to be a (g, f)-uniform graph is given and some applications of this condition are discussed. In particular, some simple sufficient conditions for a graph to be an [a, b]-uniform graph are obtained for a≤b.  相似文献   

14.
In this paper the properties of some maximum fractional [0, κ]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional κ-factors is obtained.  相似文献   

15.
PROPERTIES OF FRACTIONAL k-FACTORS OF GRAPHS   总被引:1,自引:0,他引:1  
In this paper the properties of some maximum fractional [0, k]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional k-factors is obtained.  相似文献   

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

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