首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到16条相似文献,搜索用时 109 毫秒
1.
吴亚平  王芳  范琼  毛经中 《经济数学》2004,21(3):267-271
对任一图G,其弱控制的束缚数,广义束缚数分别定义为bw(G)=min{|E‖E(∪)E(G),且γw(G-E)>γω(G)}.b'ω(G)=min{t|(A)E(∪)E(G),如果|E|=t,则有γω(G-E)>γw(G)}.在本文中我们给出了几类图的弱控制的广义束缚数的精确值,称b'ω(G)=1图为弱控制去边临界图,并研究了正则图是弱控制去边临界图的充要条件,以及一般图和树的必要条件.  相似文献   

2.
设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限制边连通二部图的充分条件.  相似文献   

3.
不含三角形的图的λ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-最优的一些充分条件.  相似文献   

4.
图的韧度与分数k-因子的存在性   总被引:1,自引:0,他引:1  
设G是一个简单无向图,若G不是完全图,G的韧度的一个变形定义为τ(G)=m in{S/(ω(G-S)-1)∶S V(G),ω(G-S)2}.否则,令τ(G)=∞.本文研究了参数τ(G)与分数k-因子的关系,给出了具有某些约束条件的图的分数k-因子存在的一些充分条件,并提出进一步可研究的问题.  相似文献   

5.
设G是一个图,若对于图G的任一条边e,都存在一个分数k-因子h,使得h(e)=1,则称图G是分数k-覆盖图.图G的孤立韧度I(a)定义为:若G是完全图,则I(C)= ∞;否则,I(G)=min{|S|/i(G-S):SCV(G),i(G-S)≥2},其中i(G-S)表示G-S中的孤立点数目.本文首次提出并研究了一个图是分数k-覆盖图与它的孤立韧度之间的关系,证明了当I(G)>k,并且δ(G)>k 1时,G是分数k-覆盖图.我们还证明了,这个结果是最好可能的.  相似文献   

6.
糙度和k—覆盖图   总被引:1,自引:0,他引:1  
一、引言 我们所考虑的图是指没有环和重边的有限无向图。在本文中未加说明的定义和记号请参见文献[2]。设G是一个具有顶点集V(G)和边集E(G)的图。对V(G)的一个子集S,用G[S]表示G的由S导出的子图且令G—S=G[V(G)\S]。若G[S]不含边,则称S为独立集。我们用d_G(x)表示G中顶点x的次数,用Γ_G(x)表示G中与顶点x邻接的顶点集合。对令.我们分别用△(G)和ω(G)表示G的顶点的最大次数和连通分支数。若对任意的且ω(G—S)>1有  相似文献   

7.
周长为3的m限制边割连通图   总被引:1,自引:1,他引:0  
如果连通图的G存在边割S,使得G-S的每一个连通分支都含有至少m个顶点,则称图G是m限制边连通的.本文刻画了周长为3的m限制边连通图.  相似文献   

8.
起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.  相似文献   

9.
设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.  相似文献   

10.
设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.  相似文献   

11.
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.  相似文献   

12.
图是超限制性边连通的充分条件   总被引:1,自引:0,他引:1  
郭利涛  郭晓峰 《数学研究》2010,43(3):242-248
设G=(V,E)是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ'(G)是G的一个最小限制性边割的基数.G是λ'-连通的,如果G存在限制性边割.G是λ'-最优的,如果λ'(G)=ζ(G),其中ζ(G)是min{d(x)+d(y)-2:xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ'.G的逆度R(G)=∑_(v∈V) 1/d(v),其中d(v)是点v的度数.我们证明了G是λ'-连通的且不含三角形,如果R(G)≤2+1/ζ-ζ/((2δ-2)(2δ-3))+(n-2δ-ζ+2)/((n-2δ+1)(n-2δ+2)),则G是超-λ'.  相似文献   

13.
图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为X'_(vd)(G).用k_(2n)-E(C_m)表示2n阶完全图删去其中一条m阶路的边后得到的图,得到了K_(14)-E(C_4),K_(16)-E(C_4),K_(18)-E(C_5),K_(20)-E(C_5)的点可区别边色数分别为14,16,18,20.  相似文献   

14.
图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.  相似文献   

15.
设 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成立.  相似文献   

16.
图的边覆盖染色中的分类问题(英文)   总被引:1,自引:0,他引:1  
设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全 r分图的分类问题  相似文献   

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

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