Rm-边割存在的一个充分条件Rm-:1673—2057(2006)06-0413—03Rm一边割存在的一个充分条件李建利,王世英(山西大学数学科学学院,太原030006)摘要:R一边割是指能将阶不小于2m的连通图G分割为各连通分支的阶都不小于m的边割,其中m取正整数,文章证明了对阶为的连通图G,若G的直径D(G)=2,且最大度??一2,则对于任意的m?【号】,G存在R-:R-边割;连通分支;直径中图分类号::,…=1时,R-边割就是传统意义下的边割;当m=2时,R--边割在通信网络的可靠性分析起了很大的作用,并引起了强烈的关注,例如文献[3]和文献[4].到目前为止,大多数的R-边割只研究了m<?Il时R-,记为D(G).本文中没有给出的术语和记号请参见文献[7].1结果定理设G是一个阶不小于的连通图,若D(G)=2,且最大度??一2,则对于任意的m?l詈l,G存在R-=1时,R-边割就是一般意义上的边割,?l詈l_l,R-边割是存在的l-,并假设G—F有个连通分支G.,G,……,,所以G—??3,不失一般l生,设F的子集F.=[V(G.),(G)]?咖,因为?3,所以G一(F\F.)=(G—F)+,,那么F的一个非空真子集F\,而G一(F\F.)的每个连通分支至少包含G—F的一个连通分支,所以F\,与F的最小性矛盾,所以=2,即G—F只有两收稿日期:2006-:国家自然科学基金(10471081)作者简介:李建利(1979一).,硕士研究生,,记为G,G2,并记X=V(G.),Y='V(G2),因为F是一边割,所以ll?i,lyl?i,若lXI>,lYI>i,则F就是一个尺…一边割,=i或lYI=i的情况,不失一般性,设II-i,因为i+1?I詈I,IxI+IyI:,所0二以lyl?i+,显然有y0y,ro?.,使得G:-),.,,结合这和G的连通性,可知G[Xu{Y}]是连通的,记F=[Xu{Y}]是连通的
Rm-边割存在的一个充分条件 来自淘豆网www.taodocs.com转载请标明出处.