3-正则3-连通图的圈上的可去边分布.pdf

年月南宁师范大学学报(自然科学版)J u n 第 卷 第期J o u r n a l o fN a n n i n gN o r m a lU n i v e r s i t y(N a t u r a l S c i e n c eE d i t i o n)V o l N o D O I:/j c n k i i s s n 文章编号:()正则 连通图的圈上的可去边分布覃城阜,杨海玲,梁宇(南宁师范大学 数学与统计学院,广西 南宁 ;南宁学院 通识教育学院,广西 南宁 ;南宁师范大学 广西应用数学中心,广西 南宁 )摘要:设G是k 连通图,e是G的一条边,由Ge经过删除度为k的顶点u,并用完全图Kk 代替导出子图(Ge)N(u)得到的图记为Ge若Ge仍是k 连通的,则称e是可去边该文证明了正则连通图的最长圈至少有条可去边,且有无穷多的例子说明这个界可达到关键词:正则 连通图;可去边;圈中图分类号:O 文献标志码:A预备知识本文中的图都是简单无向图设图G(V(G),E(G),T是顶点集V(G)的一个子集,若GT是不连通的,则称T是G的一个点割若GT中有一个分支只有一个顶点,则称T是平凡的进一步地,若|T|k,则称T是一个G的k 点割若G没有(k)点割,则称G是k 连通的设T是G的一个点割且满足|T|等于G的连通度,若A是GT中至少一个但不是所有分支的并,则称A是G的一个T 断片,记AGTA,显然A也是G的一个T 断片在不致引起混淆的情况下,简称A是G的一个断片,称断片所含的顶点个数为断片的阶设A是G的一个断片,若A中任意真子集都不是G的断片,则称A是G的一个端片设A和B是V(G)的两个不交的非空子集,记A,Bx yE(G)|xA,yB设G是k 连通图,e是G的一条边,从Ge中删除度为k的顶点u,并用完全图Kk 代替导出子图(Ge)N(u)后所得到的图记为Ge若Ge仍是k 连通的,则称e是可去的,否则称e是不可去的记ER(G)和EN R(G)分别为G中的可去边的全体和不可去边的全体若Ge中存在非平凡的(k)点割S,使得GeS恰有两个阶至少为的分支,且这两个分支分别含有x和y,则称(x y,S)是一个分离对GeS的分支A称为(x y,S)的一个边点割断片,同时称(x y,S;A)为G的一个分离集进一步地,若A不包含其他的边点割断片,则称A是一个边点割端片称恰有两个顶点的边点割断片为断片设EEN R(G),若x yE,则称分离集(x y,S;A)是一个E分离集,称A是一个E断片类似地可定义E端片图G的阶定义为G的顶点数,记作|G|关于 连通图的可去边的分布已有很多研究结果,特别是关于一些特殊子图内或特殊子图外的可去边的数目,其中特殊子图包括圈和生成树等定理设G是k 连通图,|G|k,x y是G的一条边,则x y是不可去边当且仅当存在SV(G),使得(x y,S)是G的一个分离对特别地,若k,|G|,(x y,S;A)是G的一个分离集,则S与x,y之间的每条边都是可去的基于以上结论,苏健基对 连通图中的圈上的可去边进行了研究,得到了如下结果收稿日期:基金项目:国家自然科学基金()第一作者简介:覃城阜(),男,广西河池人,教授,博士,硕士生导师,研究方向:图论通信作者简介:杨海玲(),女,广西平南人,讲师,研究方向:图论和教学管理南 宁 师 范 大 学 学 报(自 然 科 学 版)第 卷定理设G是连通图()设|G|,C是G的一个圈,则C至少有条可去边进一步地,若G还是正则的,则C至少有条可去边()设(x y,S)是G的一个分离对,Sa,b若a bE(G),则a b是可去的此外,关于 连通图的生成树的可去边数目有以下结果定理设G是连通图,若G的最小度或围长,则G的每棵生成树至少有条可去边定理设G是正则连通图,则G的每棵生成树至少有条可去边苏健基给出了 连通图可去边的数目的下界,并证明了这个界是最好的定理设G是连通图,|G|,若G不是轮W和W,则G至少有(|V(G)|)/条可去边引理设x y z是连通图G的一个三边形,若d(x)d(y)d(z),则x y,y z,x z都是可去边,且 x,y,z,Gx,y,z 中的边都是不可去的引理设G是一个连通图,x yEEN R(G),(x y,S;A)是一个E分离集,令Sa,b,A是一个E端片若|A|,则如下的()或()成立:()(E(A)A,S)E,()G中存在一个分离集(xy,S;A),Sa,b,xyE,使得Ax,a,AAx,ASa,ASa,SAb,且ASb本文主要研究 正则 连通图的圈上的可去边分布情况,将证明 正则 连通图的最长圈至少有条可去边,并给出例子说明这个界是可达到的主要结果以下均设G是 正则 连通图引理设(x y,S;A)是G的一个分离集,Sa,b,C是G的一个圈若Ax,z 是一个断片,则有()若x y在圈C上,则E(C)E(A)ER(G)()若x y在最长圈C上,则|E(C)E(A)ER(G)|证明()不失一般性,设a xE(G),则x z a是一个三边形,由引理知x a,z a,x z都是可去边另一方面,圈C经过x a或x z因此C必有可去边()因为C是最长圈且x yE(C),所以x a和a z都包含在C中,或x z和a z都包含在C中,故结论成立定理设|G|,C是G的一个圈,若GCER(G)是连通的,则C至少有条可去边证明由定理 知C至少有条可去边设|E(C)ER(G)|,Cyyyk yky若k,则C是一个三边形,由引理知C的边都是可去的,于是结论成立下设k因为GCER(G)是连通的,所以假设yy,yyk是可去边设Eyy,yy,yk yk,取(yiyi,S;A)是一个分离集,使得A是一个E端片,令Sa,b断言|A|否则,|A|即Ayi,z 是一个端片进一步地,令Sa,b,a yiE(G)则由引理,包含在三边形yiz a中的边是可去的,yi,z,a,V(Gyi,z,a)中的边都是不可去的因为yiyi 在圈C上,所以yiz或yia在圈C上即三边形yiz a中至少有条边包含在C上现有(E(A)A,SA,S)ER(G)E(C)我们取分离集(ytyt,S;A),使得AA,且A是一个E端片显然,(E(A)A,S)ER(G)E(C)若|A|,则由引理可知,(E(A)A,S)ER(G)E(C),矛盾所以|A|另一方面,由引理,存在分离集(ylyl,S;A)使得AAS且|A|由引理得第期覃城阜,等:正则 连通图的圈上的可去边分布(E(A)A,S)ER(G)E(C),矛盾故断言成立由断言,假设每个E端片的阶至少为 设A是一个E端片,则A至少有个顶点若(E(A)A,S)EN R(G)E(C),则由引理 可知,AS中存在分离集(ylyl,S;A)使得|A|,矛盾所以(E(A)A,S)EN R(G)E(C),因此(E(A)A,S)E(C)ER(G)断言(E(A)A,S)ER(G)E(C)若(E(A)A,S)ER(G)E(C),则可取分离集(ytyt,S;A)使得AA且A是一个E端片所以(E(A)A,S)ER(G)E(C)显然,|A|由引理知,存在分离集(ylyl,S;A)使得AAS且|A|,矛盾因此断言成立现由(E(A)A,S)E(C)ER(G),(E(A)A,S)ER(G)E(C),我们知道存在uS使得u a,u aER(G)E(C),这里aA,aA注意到(E(A)A,S)E(C)ER(G),所以ayi若N(u)Aa,易知SSau是G的一个点割,矛盾所以假设|N(u)A|即|N(u)A|设AAu,SSau则我们知道(yiyi,S;A)是一个分离集,使得yiyi E由此可推断出(E(A)A,S)ER(G)E(C)取(ytyt,S;A)是一个分离集,使得AA且A是一个E端片现在我们知道(E(A)A,S)ER(G)E(C)由断言,显然|A|另一方面,由引理知,存在分离集(ylyl,S;A),使得AAS且|A|,矛盾定理证毕设GN(V(G),EN R(G)表示G中由不可去边集导出的子图由定理可得如下推论(已由康海燕等证明)推论设|G|,则G的每棵生成树至少有条可去边证明由定理知,GN的每个分支都是树进一步,由定理,GN至少有两个分支下面我们证明GN至少有个分支假不其然,设GN恰有两个分支,记为H和H令x是H的一个顶点,使得dH(x)因为dH(x),所以可假设x x和x x是可去边若xV(H),则G有一个恰包含一条可去边的圈,矛盾因此xV(H),同理xV(H)设P是H中唯一连接x和x的路现有CPx x,x x 是一个圈,使得GCER(G)是连通的,且|E(C)ER(G)|,矛盾因此GN至少有三个分支,由此可得结论定理设C是G的最长圈,则C至少有条可去边证明设EE(C)EN R(G)我们取(x y,S;A)为G的一个分离集,使得A是一个E端片断言|(E(A)A,S)ER(G)E(C)|若|A|,则由引理,有|E(A)A,SER(G)E(C)|因此设|A|若(E(A)A,S)EN R(G)E(C),则由引理,存在分离集(ylyl,S;A),使得AAS,ylyl E且|A|由引理可知|(E(A)A,S)ER(G)E(C)|所以可假设(E(A)A,S)E(C)ER(G)若|(E(A)A,S)E(C)|,则断言成立故可设|(E(A)A,S)E(C)|令(E(A)A,S)E(C)x x,由C是一个圈可知xS另一方面(E(A)A,S)E,由此可知Ax 不包含C的顶点若N(x)Ax,则Sxx 是一个点割,矛盾所以令N(x)Ax,a设P是A中连接x和a的路,现知CPx a 是一个更长的圈,矛盾断言证毕由断言知|(E(A)A,S)ER(G)E(C)|G中也存在一个分离集(xy,S;A),使得AA且xyE由断言,我们知道|(E(A)A,S)ER(G)E(C)|显然(E(A)A,S)E(A)A,S由此知定理的结论成立 南 宁 师 范 大 学 学 报(自 然 科 学 版)第 卷例考虑如图所示的正则连通图G显然,G中的粗边都是可去边,其他的边都是不可去边注意到圈Ca xxxnb a恰有两条可去边,圈Ca yyykxkxk xa恰有条可去边,圈Ca xxxnb ynyn yya恰有条可去边可见定理和定理所得的结果是最好的图参考文献:H o l t o nDA,J a c k s o nB,S a i t oA,e t a l R e m o v a b l e e d g e s i n c o n n e c t e dg r a p h sJ J o u r n a l o fG r a p hT h e o r y,():苏健基连通图中圈上的可去边J科学通报,():吴吉昌,李学良连通图生成树上的可去边J兰州大学学报,():欧见平,苏健基连通图的可去边的分布J广西师范大学学报(自然科学版),():欧见平,苏健基连通图的可去边数J应用数学,():F o u q u e t J,T h u i l l i e rH O nr e m o v a b l e e d g e s i n c o n n e c t e dc u b i cg r a p h sJ D i s c r e t eM a t h e m a t i c s,():S uJ T h en u m b e ro f r e m o v a b l ee d g e s i n c o n n e c t e dg r a p h sJ J o u r n a l o fC o m b i n a t o r i a lT h e o r y(S e r i e sB),():K a n gH Y,WuJC,L iGJ R e m o v a b l ee d g e so f a s p a n n i n g t r e e i n c o n n e c t e d r e g u l a rg r a p h sJ L e c t u r eN o t e si nC o m p u t e rS c i e n c e,:吴吉昌,李学良 连通 正则图生成树外的可去边(英文)J数学研究,():D i s t r i b u t i o no fR e m o v a b l eE d g e si nt h eC y c l e so f R e g u l a r C o n n e c t e dG r a p h sQ I NC h e n g f u,YAN G H a i l i n g,L I AN GY u(S c h o o l o fM a t h e m a t i c sa n dS t a t i s t i c s,N a n n i n gN o r m a lU n i v e r s i t y,N a n n i n g ,C h i n a;C o l l e g eo fG e n e r a lE d u c a t i o n,N a n n i n gU n i v e r s i t y,N a n n i n g ,C h i n a;C e n t e r f o rA p p l i e dM a t h e m a t i c so fG u a n g x i,N a n n i n gN o r m a lU n i v e r s i t y,N a n n i n g ,C h i n a)A b s t r a c t:L e tGb eak c o n n e c t e dg r a p ha n dea ne d g eo fG D e n o t eb yGet h eg r a p ho b t a i n e df r o mGeb yd e l e t i n ge a c hv e r t e xuo f d e g r e ek i nGea n dr e p l a c i n g t h e i n d u c e ds u b g r a p h(Ge)N(u)w i t ht h e c o m p l e t eg r a p hKk A ne d g eei s s a i d t ob e r e m o v a b l e i fGei s a l s ok c o n n e c t e d W es h o wt h a t e a c hl o n g e s tc y c l eo fa c o n n e c t e dc u b i cg r a p hh a sa t l e a s t f o u rr e m o v a b l ee d g e s,a n dt h e r ea r e i n f i n i t e l ym a n yg r a p h s t h a t a t t a i nt h i sb o u n d K e yw o r d s:c o n n e c t e dc u b i cg r a p h;r e m o v a b l ee d g e;c y c l e 责任编辑:班秀和 责任编辑:彭喻振