3-正则3-连通图的圈上的可去边分布.pdf
《3-正则3-连通图的圈上的可去边分布.pdf》由会员分享,可在线阅读,更多相关《3-正则3-连通图的圈上的可去边分布.pdf(4页珍藏版)》请在咨信网上搜索。
1、 年月南宁师范大学学报(自然科学版)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,并
2、用完全图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 断片
3、,记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恰有两个阶至少为的分支,且这两个分支分别含有
4、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
5、)是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
6、),则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|,则
7、如下的()或()成立:()(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,
8、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 是一个端片进一步地
9、,令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)
10、,矛盾故断言成立由断言,假设每个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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 正则 连通 可去边 分布
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。