共查询到14条相似文献,搜索用时 109 毫秒
1.
设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)-临界图. 相似文献
2.
设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)的性质. 相似文献
3.
《数学的实践与认识》2013,(13)
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是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 . 相似文献
5.
设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相似文献
6.
本文首先给出了(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-覆盖图的一个充分必要条件. 相似文献
7.
8.
9.
设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)-因子的充要条件,并据此,得到了一些有趣的结果。 相似文献
10.
设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]中的一个结果。 相似文献
11.
(mg+m—1,mf—m+1)—图的(g,f)—因子 总被引:8,自引:0,他引:8
本文证明了(mg+m-1,mf-m+1)-图具有一些特殊的(g,f)-因子,从而推广到了关于(g,f)-覆盖图和(g,f)-消去图的有关结果,有助于进一步研究(mg+m-1,mf-m+1)-图的正交因子分解问题。 相似文献
12.
On (g, f)-Uniform Graphs 总被引:3,自引:0,他引:3
Gui-zhenLiu YanLiu 《应用数学学报(英文版)》2005,21(1):67-76
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. 相似文献
13.
LIU Guizhen & DENG Xiaotie Department of Mathematics Shandong University Jinan China Department of Computer Science The City University of Hong Kong Hong Kong China 《中国科学A辑(英文版)》2005,48(3)
Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x)≤ f(x) for every vertex x of V(G). A (g. f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g. f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible. 相似文献
14.
分数因子和分数哈密顿图 总被引:1,自引:0,他引:1
本文介绍了图的分数方面,将图中基于整数的定义和变量转化为分数形式.介绍了分数图论的一些新结果,特别是关于分数因子和分数哈密顿图的新结果,其中包括了作者最近得到的一些关于分数(g,f)-因子的若干结果.进而,提出了还没有解决的几个新问题. 相似文献