ð Þð ÞJournalof the Egyptian Mathematical Society（2015）23，215埃及数学学会埃及数学学会www.etms-eg.orgwww.elsevier.com/locate/joems短通信关于太阳图族和轮图族的bJ. Vernold Vivina，*，M. Vekatachalamba印度泰米尔纳德邦Nagercoil 629b印度泰米尔纳德邦哥印拜陀641 402RVS工程学院RVS教育信托机构集团数学系接收日期：2013年11月6日;修订日期：2014年3月15日;接受日期：2014年2014年6月30日在线提供图的适当着色给图的顶点、边或两者都赋以颜色，从而使邻近元素被赋以不同的颜色。图着色的概念和问题自然产生于实际问题，并在许多领域中得到应用，包括信息论和最著名的理论计算机科学。图G的b-染色是图G的真染色，G的顶点，使得每个色类中存在一个顶点连接到每个其他色类中的至少一个顶点。图G的b-色数记为uG，是使得G可以有k种颜色的b -染色的最大整数k.本文给出了太阳子图Sn、太阳子图L<$Sn<$的线图、太阳子图M <$Sn <$的中图、太阳子图T <$Sn <$的全图、轮图M<$Wn<$的中图以及全图的b轮图TW n。1991年数学次级分类：05C15; 05C75; 05C76？2014制作和主办Elsevier B.V.埃及数学学会的代表1. 介绍本文所考虑的所有图都是非平凡的、简单的和无向的。设G是一个顶点集为V，边集为E的图.图G的k-染色是 图G 的一个划分P ^fV1; V2;. ; V kg*通讯作者。联系电话：+91 9566326299。电子邮件地址：vernoldvivin@yahoo.in，vernold_vivin@yahoo.com（J.VernoldVivin），venkatmaths@gmail.com（M.Vekatachalam）。同行评审由埃及数学学会负责的独立集合G。G有k-染色的最小基数k是G的色数vnG_n. b-色数uG[1-4]的一个图G是最 大 的 正 整 数 k ， 使 得G 允 许 一 个 正 常 的 k - 染 色 ， 其 中 每 个 色 类 都 有一 个 代 表 性 的 a d j a ，center到每个其他颜色类别中的至少一个顶点。这样的着色称为b-着色. b-色数是由Irving和Manlove [1]通过考虑相对于定义在V G的所有划分的集合上的偏序是最小的适当着色而引入的。他们已经表明，确定uG一般情况下是NP难的吗图，但树的多项式日益增加自从[1]发表以来，人们对b-着色的研究产生了浓厚的兴趣。1110- 256 X？ 2014制作和主办Elsevier B. V.埃及数学学会的代表http://dx.doi.org/10.1016/j.joems.2014.05.011制作和主办：Elsevier关键词b-染色;太阳子图;轮图;中图;全图和线图¼¼ð Þþ-ðÞ¼ð Þð Þ¼þÞ ð Þ216 J. Vernold Vivin，M. 韦卡塔查兰Irving和Manlove[1]也证明了u∈G∈ G的上界uG6DG11Kouider和Mahe′o[5]给出了两个图的卡积的b -色数的上、下界。 KratochvJ'letal. [6]刻画了连通二部图的b-染色数的下界，并证明了连通二部图是否存在控制真b -染色的NP-完全性。Effantin和Kheddouci研究了[7-Faik[10]对b-染色的连续性很感兴趣，并证明了弦图是b-连续的.Corteel等人[11]证明了b-色数问题对于任何s>0在120=133s内是不可逼近的，除非P NP。Hoang′ng和Kouider在[12]中刻画了G的每个导出子图H都有uHvH的二部图和P4-稀疏图.Kouider和Zaker[13]提出了一些上界，几类图的b-色数是其它图参数（团数、色数、双团数）的函数。Kouider和El Sahili在[14]中证明了：如果G是围长为5的d -正则图，且没有长度为6的圈，则uG d 1.Jakovac和 KlavzZhaiar[2]证明了b-色数除Petersen图、K3;3、K3上的棱柱图和10点零星图Effantin和Kheddouci[15]讨论了这个参数与另外两个着色参数（Grundy数和部分Grundy数）之间的关系。 b-着色中的支配节点的性质是非常有趣的，因为它们可以直接与图的每个部分通信。最近，VernoldVivin和Venkatachalam[4]证明了任意两个图的晕的b作者还研究了星图族的b-色数[3].2. 预赛通过在2n个顶点上附加n个顶点，得到了2 n个顶点的n-sunlet图环Cn的悬边，记作Sn。对任意整数nP 4，轮图W n是通过将顶点v1连接到n-1个顶点fw1;w2;. ;wn-1g的圈图Cn-1.图G的线图[16]，记为L<$G<$，是顶点是G的边的图，如果u;v2E<$G<$，则uv2E<$L<$G<$<$，如果u和v在G中共享一个顶点.设G是一个顶点集为V，边集为E的图. G的中间图，记为M G，定义如下。M. M <$G <$的两个顶点x;y在M<$G<$中相邻，如果下列之一成立：(i)x;y在E∈G∈ G中，x;y在G中相邻。（ii）x的单位为VG;y是在E中的，x;y是在G中关联的。设G是一个顶点集为V，边集为E的图. G的全图[16]，记为TG，定义在遵循的方式。T. T <$G <$的两个顶点x，y在T<$G <$中相邻，如果下列条件之一成立：（i）x，y在V<$G<$中，且x在G中与y相邻. （ii）x;y在E∈G∈ G中且x;y在G中相邻.（iii）x在V<$G<$;y在E<$G<$;x;y在G中关联。3. Sunlet图及其线图、中图和全图的b-染色定理1. 设n为P6。则太阳子图的b-色数为uSn4。证据设Sn是2n个顶点的太阳子图 设V=1; V= 2;. ; v ng[ fu1;u2;. 其中v i是按循环顺序取的循环的顶点，u i是悬垂顶点。使 得 每 个 Vi ui 是 悬 垂 边 。 考 虑 Sn 的 以 下 4- 着 色 ：c1;c2;c3;c4n，将颜色c1赋给vn;c2赋给v1;c3赋给v2;c4赋给v3;c2赋给v4;c4赋给vn-1;c3赋给un;c4赋给u1，26i6n- 1，将颜色c1分配给ui。对于56i6n- 2，如果有的话，给顶点vi分配一种允许的颜色-这样的颜色存在，因为degvi=3。一个简单的检查表明，这个着色是一个b-着色.因 此 ，uSnP4（见图4）。①的人。由于D=Sn=1/3，使用1：1，我们得到u=Sn=6/4。因此，我们认为，u=Snnn1 /4，对于所有nP6。 H定理2. 设n为P6。则sunlet图的线图的b-色数为uLSn<$<$5。证据设V=1;v= 2;. . ;v ng[fu1;u2;. 其中ei是边v ivi116i6n-1;en是边v n v1，e0i是边v i u i16i6n -1。根据线图VLSn 的 定 义，其中v 0 i和u0i分别表示边ei和e0i=16i6n - 1g [fv0i：16i6n-1g[fv0ng]。考虑LSn 的 以下5-着色：c1;c2;c3;c4;c5，将颜色c5分配给u01;c4分配给u02;c5分配给u03;c1分配给u04; c2分配给u05; c1分配给u06; c3分配给v0n; c3分配给v06，对于1 6 i 6 5，将颜色c i分配给v0i。对于76i6n，将颜色c2分配给u0i。为图1太阳黑子图Snð Þ¼ð Þ¼ð Þ关于太阳图族和轮图族的b-色数图2Sunlet图L<$S n <$的线图。如果有的话，将允许的颜色之一分配给顶点v0i-这样的颜色存在，因为deg v0i4 。 一 个 简 单 的检查表明，这个着色是一个b-着色.因此，uLSnP5。由于DLSn4，使用1：1，我们得到uLSn65。因此，对于所有的n P 6，uLSn1/5（见图2）。 2）的情况。H定理3. 设n为P 9。则sunlet图的中间图的b-色数为u<$M <$Sn<$7。证据 让VS fv;v;. ;vg[fu;u;. . ;ug和图3Sunlet图M<$S n <$的中间图。4. 轮图的中全图的b-染色定理5. 设n为P 7。则轮图的中间图的b-色数为un;n是Wn中的顶点数。证据设V_n=v;v1;v2;. . v n-1g且令VMW nfv; v1; v2;. . v n-1g [fe1;e2;. e n-1g [fu1; u2;.. . u n-1g. 其中ui是MWn的顶点，对应于n12n12NWn<$16i6n-1<$，ei是M<$Wn<$对应的顶点E是边v n v 1，e0i是边vuin1，e0i是边v u in1。通过定义中间图VMS nn VS n[ES n] fv i：1 6i6ng[ fu i：1 6 i6ng[fv0i：16i6n g [fu0i：16i6ng，其中v0i 而u0i分别表示边e i和e0i 16 i6 n。 考虑M S n的以下7-着色：c1; c2; c3; c4; c5; c6; c7，将颜色c7赋给v0n; c6赋给u01; c1赋给v01; c3赋给v1; c5赋给u02; c2赋给v02; c4赋给v2; c3赋给v03;c7赋给u03;c6赋给v3;c1赋给v4;c5赋给u04;c4到v04;c2到v5;c7到u05; c6到v05; c3到u06; c1到v6; c5到v06; c4到u07; c2到v7 ; c7到v0 7; c3到u 08; c1到v8; c6到v08，并且对于1 6 i 6 n，将允许的颜色之一分配给顶点u i-这样的颜色存在，因为deg u i1.一、对于96i6n，如果有的话，给顶点vi和顶点ui赋值以下之一：允许的颜色-这种颜色存在，因为degvi=3。对于96i6n- 1，为顶点v0i指定一种允许的颜色-这样的颜色存在，因为degui= 1/46。简单地检查一下就可以看出这是一种B色. 这是e，umsnP7。由于DMSn6，使用1：1，我们得到uMSn67。因此，对于所有n P 9，uMSn1/47（见图2）。 3）。 H定 理 4. 设 n 为 P 9 。 则 sunlet 图 的 全 图 的 b- 色 数 为uTSn<$<$7。证据考虑在定理3的证明中引入的MS n的着色。一个简单的检验表明这个染色是T Sn的一个b-染色. 因此，对于所有n P 9，u∈T∈Sn∈P7。由于DTSn6，使用1：1，我们得到uTSn67。因此，对于所有的n P 9，uTSn1/47（见图2）。 4）.H到W n= 16i6n-1 n的边vv i。通过中图的定义，使顶点v和fei：16 i6 n-1 g在MWn中导出一个n阶图. 因此，uMWnPn。 考虑下面的n-着色MW n。对于16i6n-1，指定颜色c i到ei和 分配 的 颜色 Cn到v. 对于16i6n- 1，为顶点ui指定一种允许的颜色-这样的颜色存在，因为degui= 1/46。对于16i6n-1，如果图4Sunlet图TS n的全图。þðÞðÞð Þ ð ð ÞÞ ¼8218J. Vernold Vivin，M. 韦卡塔查兰确认作者谨对裁判引用图5车轮MWn1的中间图。图6车轮TWn1的总图形。任何，分配给顶点vi一个允许的颜色-这样的颜色存在，因为度vi=3。一个简单的检查表明，这个着色是一个b着色。因此，uMWnPn。假设u大于n，则M W n中必须至少有n 1个n度顶点，所有顶点都具有不同的颜色，并且每个顶点都与所有其他颜色的顶点相邻。对于nP6，这是一个矛盾。因此，我们有uMWn6n。因此，我们认为，uMWnn;8nP7（请参阅图5）。H定理6. 设n为P 7。则轮图的全图的b-色数为uTWnn nn;n是W n中的顶点数。证据考虑在定理5的证明中引入的M W n的着色。一个简单的检验表明，这个染色是TWn的b-染色.因此，uT W nn;nP6（见图6）。H[1] R.W.欧文，D.F.张文，张文辉，张文辉，等.[2] M. Jakovac ， S.Klavzar ， 三 次 图 的 b- 色 数 ， GraphsComb.26（1）（2010）107-118.[3] M. Venkatachalam，J. Vernold Vivin，星图族的b-色数，LeMatematiche 65（1）（2010）119-125。[4] J. Vernold Vivin，M. Venkatachalam，电晕图的b-色数，Utilitas Math.88（2012）299-307。[5] M. Kouider，M. 张文辉，等.图的b-色数的几个界.离散数学，2002（1-2）.[6] J. KratochvZ.L.，Z. 图扎湾Voigt，关于图的b-色数，见：第28届国际计算机科学图论概念研讨会，第2573卷，捷克克鲁姆洛夫，LNCS，2002年，第100页。310-320[7] B.李文，李文，等.完全毛虫图的B -色数.数学学报，2000，24（1）：117 - 118. Cryptogr. 8（3）（2005）483-502。[8] B. Effantin，H.张文，李文，李文，等. Theor. Comput. Sci.6（2003）45- 54。[9] B. Effantin，H.张文，张文辉，张文辉，等.幂完备k叉树的b -色数的精确值.数学学报，2000，21（1）：117 - 118.Cryptogr. 8（1）（2005）117-129。[10] T.张文，关于图的b-连续性，《离散数学札记》，第17期（2004），第151-156页.[11] S. Corteel，M.Valencia-Pabon，J.C.维拉，在近似b-色数，离散应用数学 146（2005）106-110。[12] C. 好啊，M。张文龙，图的b-控制染色，《离散应用数学》，第152期（2005）.[13] M. Kouider，M.张文龙，等.[14] M. Kouider ， A. El Sahili ， 关 于 正则图的b- 着 色 ，RapportdeRecherc h e No1432 ， CNRS-U niversite'ParisSud-LRI，2006，02/2006。[15] B. Effantin，H.张文，张文辉，等.图的（部分）Grundy数和b-色数的讨论.实用数学，80（2009）65-89.[16] F. Harary ， Graph Theory ， Narosa Publishing Home ，NewDelhi，1969。
我的内容管理
展开
