圈的三种积图的b-染色与b-边染色.pdf
《圈的三种积图的b-染色与b-边染色.pdf》由会员分享,可在线阅读,更多相关《圈的三种积图的b-染色与b-边染色.pdf(5页珍藏版)》请在咨信网上搜索。
1、第44卷总第13 1期2023年9 月西北民族大学学报(自然科学版)Journal of Northwest Minzu University(Natural Science Edition)Vol.44,No.3Sep,2023圈的三种积图的 b-染色与b-边染色钟闯,田双亮(西北民族大学数学与计算机科学学院,甘肃兰州7 3 0 0 3 0)摘要设是G的一个k-点染色,若在G中一定存在一个点,使得该点在其他k-1个色类中都至少有一个邻居,则称该点为b点,称。为G的一个b染色.其中,最大的k值称为G的b-色数,记为g(G).设是G的一个k-边染色,若在G中一定存在一条边,使得该边在其他k1个色
2、类中都至少有一个邻居,则称该边为b边,称为G的一个b-边染色。其中,最大的k值称为G的b-边色数,记为(G).关键词b染色;b边染色;运算图;正则图中图分类号0 0 1文献标识码A文章编号10 0 9-2 10 2(2 0 2 3)0 3-0 0 0 1-0 50引言本文讨论的图均为有限无向简单连通图,分别用V(G)、E(G)和(G)表示图G的顶点集、边集和最大度,用dc()表示G中顶点的度数.本文未说明的符号及术语可参见文献1.b-染色是由Irving和Manlove于1999年在文献2 中提出的新染色概念,研究的是图中顶点的最大分类问题.该染色主要用于解决不同社区间的通讯问题.所谓b染色是
3、指。=(Vi,V2,,V)是G的一个k-点染色,使得每个颜色类V;,i=1,2,,k中都至少包含一个顶点,使得该点在其他k-1个颜色类中都至少有一个邻点,则称该点为b点,为G的一个b-染色.其中,最大的k值称为图G的6-色数,并记为(G).设 U,U2,U是G 中的一个点序列,且d()d(2)d(n),那么 m(G)=max(i:d(;)i 1)就是p(G)的一个上界.类似地,与b染色对应的b-边染色的概念是由Jakovac和Peterin于2 0 15年在文献3 中提出的.设。=(Ei,E,,E)是G的一个k-边染色,若每个颜色类E;,i=1,2,k 中都至少包含一条边,使得该边在其他的k-
4、1个颜色类中都至少有一条邻边,称该边为b边,为图G的一个b-边染色,其中最大的k值称为图G的b-边色数,并记为(G).G的b-边色数的平凡上界m(G)=max(i:d(e;)i-1),其中d(ei)d(e)d(em)是G中边ei,e2,em的一个度序列.对于一般图G来说,研究它的b边染色问题等价于研究它的线图L(G)的b染色问题.若G是d-正则图,那么它的线图L(G)是2 d-2-正则图属特殊情况.关于正则图的b染色问题目前已有相关研究,如Kratochvil等人于2 0 0 2 年在文献4中证明了阶数至少为d4的d-正则图G的b-色数为d十1.事实证明,这个阶数的边界可能会比d4小,比如4阶
5、圈与2阶路的笛卡尔积是3-正则的,但是它的b色数是4.2 0 11年,Sergio等人在文献5中对Kratochvil提出的图的阶数下界进行了优化,即阶数至少为2 d的任意d-正则图的b-色数为d十1.之后,Sahili等在收稿日期2 0 2 3-0 4-17通信作者田双亮,男,教授,主要从事组合数学与图论方面的教学研究.作者简介钟闯,女,蒙古族,硕士研究生,主要研究方向为组合数学和图论.文献6 中优化了Cabello等人给出的约束条件,即满足d7且阶数至少为2 d3十2 d-2d的d-正则图的b色数为d十1.但是对于一些特殊的正则图,如两个圈的直积是4-正则的,它的度是严格小于7 的,那么它
6、的b色数是否还是d十1?关于更多d-正则图的b-染色的研究可参见文献7 10.由于b边染色概念提出较晚,所以与正则图相关的研究还比较少,如Jakovac等人于2 0 15年在文献11中给出了围长至少为5的d-正则图的6-边色数为2 d一2.同年,Koch等人在文献12 中给出了部分正则图直积的b边色数的上界和下界.本文主要研究:阶数不满足2 d的d-正则图的b-色数也为d十1,同时给出围长小于5的d-正则图的b边色数也为2 d一1.其中,研究的主要图类是两个圈的三类积图.本文研究的结构运算有图的笛卡尔积、直积、强积,具体的定义如下:称GH是简单图G与H的笛卡尔积,其顶点集是V(G)V(H).顶
7、点(ul,U i)与(u2,2)相邻当且仅当 uiu E(G)且 =或者 i E(H)且 ui=u2.称GXH是简单图G与H的直积,其顶点集是V(G)XV(H).顶点(ui,U i)与(u2,U 2)相邻当且仅当uiu E E(G)且 iU E E(H).我们称GH是简单图G与H的强积,其顶点集是V(G)V(H).顶点(ui,)与(u2,U 2)相邻当且仅当 ui u E(G)且 iU E E(H)或者 u u E E(G)且 i=2 或者 Vi 2 E E(H)且 u=uz.为了叙述方便,在两个圈的积图中用(,y)来表示顶点(u,),用(ayay)表示边(,y)(,y).下文要用到以下引理:
8、引理0.1对于任意简单图G,有(G)(G)m(G)(G)十1.引理 0.2对于任意简单图 G,有(G)(G)(G)m(G)2(G)-1.1主要结果及其证明关于两个圈的直积的6 染色有以下结果.定理1.1对任意的整数m4,n8,有g(CmC,)=5.证明设设Cm=uo ui um-1 uo,C,=o U1Uu-1 Uo,并记G=Cm XCn.由引理 0.1可知,p(G)(G)十1=5.为证明(G)5,需证明G存在一个5-b-染色.令G是G的一个导出子图(见图1),其顶点集V。=(,)0 6,0 2).分两步构造G的一个5-b-染色.(0,2)(1,2)(2,2)(3,2)(4,2)(5,2)(6
9、,2)(0,1)(6,1)(0,0)先构造G的一个部分染色,具体地,对每一顶点(,)V。,令(,)=(十2)5.显然,染色所用的颜色集合为(0,1,2,3,4).首先,验证G的部分染色。是正常的.由。的定义容易证明V。中的顶点与其邻点是染不同颜色的.事实上,对于任意顶点(,y)EV。,其可能的邻点有:(-l,-1),(+l,y+1),(-l,y+1),(+l,y1).假设(,)=(一1,一1),则(3)=,这是不可能的.所以,()(l,1).同理可证,顶点(,y)与其他邻点也是异色的.然后,证明每一色类中都至少包含一个b点.由于G中顶点的度都为4,那么仅需证明每一色类中2(1,0)图1G的导出
10、子图G。(2,0)(3.0)(4,0)(5,0)(6,0)(-l,y),(,y+1),(,y-l),(+l,y).都至少存在一个点,使得该点的邻点都是异色的.事实上,每一颜色集合Vi,i=0,1,2,3,4都包含一个顶点(,1),=1,2,3,4,5,i=(十2)且对于顶点(,1)的邻点有(一1,2)=(十3)(十l,2)=(十5)5(1,0)=(1)5(十1,0)=(+1)5.容易验证,顶点(,1),=1,2,3,4,5的任意两个邻点都异色,所以顶点(,1),=1,2,3,4,5是色类i,i=(十2),的一个b点.因此是V。的一个b染色.最后,根据贪婪算法可将部分染色拓展到V(G)中的所有点
11、.这样,就是G的一个5-b-染色,因此,(G)=5.关于两个圈的笛卡尔积的6 染色有以下结果.定理1.2 对任意的整数m4,n8,有(C,C,)=5.证明设 Cm=uouim-1uo,C,=oiU,-1Uo,并记G=CmCn.由引理 0.1 可知,(G)(G)十1=5.为证明(G)5,需证明G存在一个5-b-染色.取V(G)的一个子集V。=(,y)|0 6,02).现在分两步构造G的一个5-b-染色.先构造G的一个部分染色,具体地,对每一顶点(,)V。,令(,)=(十2 y)5.显然,染色所用的颜色集合为0,1,2,3,4).首先,验证G的部分染色是正常的.由的定义容易证明V。中的顶点与其邻点
12、是染不同颜色的.事实上,对于任意顶点(,y)EV。其可能的邻点有:假设(,)=(一l,),则(1)=,这是不可能的.所以,(,)(一l,).同理可证,顶点(,y)与其他邻点也是异色的.然后,证明每一色类中都至少包含一个b点.由于G中顶点的度都为4,那么仅需证明每一色类中都至少存在一个点,使得该点的邻点都是异色的.事实上,每一颜色集合V,i=0,1,2,3,4都包含一个顶点(,1),=1,2,3 4,5,i=(十2),且对于顶点,1)的邻点有(一1,2)=(十3)5(十1,2)=(+5)5(1,0)=(1)5(+1,0)=(+1)5.容易验证,顶点(,1),=1,2,3,4,5的任意两个邻点都异
13、色,所以顶点(,1),=1,2,3,4,5是色类i,i=(十2)的一个b点.因此是V。的一个6 染色.最后,根据贪婪算法可将部分染色拓展到V(G)中的所有点.这样,o就是G的一个5-b-染色.因此,p(G)=5.关于两个圈的强积的6 染色有以下结果.定理1.3 对任意的整数m,n 5,有(C m C,)=9.证明设Cm=uo ul m-1uo,C,=UoUi,-1Uo,并记G=CmC,.由引理 0.1 可知,p(G)(G)十1=9.为证明(G)9,需证明G存在一个 9-b-染色.令 H=PPs,取V(G)的一个子集V(H)=(,)0,4).现在分两步构造G的一个9-b-染色.先构造G的一个部分
- 配套讲稿:
如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。