共查询到17条相似文献,搜索用时 101 毫秒
1.
2.
3.
图的孤立韧度与分数因子的存在性 总被引:10,自引:1,他引:9
设G是一个简单无向图,若G不是完全图,G的孤立韧度定义为I(G)=min{|S|/I(G-S):S包含于V(G),I(G-S)≥2}。否则,令I(G)=∞。本文引入一个与图的孤立韧度I(G)密切相关的新参数I‘(G),若G不是完全图时,I‘(G)=min{|S|/(I(G-S)-1):S包含于V(G),I(G-S)≥2}。否则,I‘(G)=∞;本文研究了参数I(G)和I‘(G)的性质以及两者与图的分数k-因子的关系。给出了具有某些约束条件的图的分数因子存在的一些充分条件。并提出进一步的可研究的问题。 相似文献
4.
设G是一个简单的无向图,若G不是完全图,G的孤立韧度定义为I(G)=min{|s|/i(G-S):S∈V(G),i(G-S)≥2);否则令I(G)=∞.对与图的孤立韧度I(G)密切相关的新参数,I’(G),若G不是完全图,定义I’(G)=min{|s|/i(G-S)-1:S∈V(G),i(G-S)≥2};否则I’(G)=∞本文研究了新参数I‘(G)与图的分数κ-因子的关系,给出了具有某些约束条件的图的分数κ-因子存在的一些充分条件. 相似文献
5.
6.
图的分数因子与孤立韧度 总被引:3,自引:0,他引:3
图G的孤立韧度定义为I(G)=min{|S|/i(G-S)∶SV(G),i(G-S)≥2},若G不是完全图.否则令I(G)=∞.本文给出了图的分数k因子与图的分数[a,b]因子的存在性与图的孤立韧度的关系.证明了,若δ(G)≥k且I(G)≥k,则G有分数k因子;若δ(G)≥I(G)≥a-1 a/b,则图G有分数[a,b]因子,其中a相似文献
7.
8.
杨宏晨 《数学的实践与认识》2003,33(11):131-135
图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 . 相似文献
9.
10.
分数k-因子临界图的条件 总被引:1,自引:0,他引:1
设G是-个连通简单无向图,如果删去G的任意k个项点后的图有分数完美匹配,则称G是分数k-因子临界图.给出了G是分数k-因子临界图的韧度充分条件与度和充分条件,这些条件中的界是可达的,并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件. 相似文献
11.
张磊 《数学的实践与认识》2021,(1):302-307
设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件. 相似文献
12.
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. 相似文献
13.
不含三角形的图的λ3-最优性的充分条件 总被引:1,自引:0,他引:1
设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件. 相似文献
14.
Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n. 相似文献
15.
贺东奇 《数学的实践与认识》1999,(4)
设G是一个n阶3-连通图,周长为C(G),独立数为,若G是1-坚韧的,且,则G的每一个最长圈是控制圈且;又若G是5/3-坚韧的或,则G是Hamilton图。 相似文献
16.
设 G是一个图,若对于 G的任意一边 G都有{P_2,Ci|i->3}-因子含有这条边,则称G是{P_2,Ci|i->3}-覆盖图.本文给出连通非二分图G是{P2,Ci|i->3}-覆盖图的充要条件为任给S■V(G),V(G)≠S≠■有i(G-S)_>|S|-1成立. 相似文献
17.
令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-边-可消去的与韧度和孤立韧度相关的充分条件。证明了这些结果在一定意义上是最好可能的. 相似文献