APP下载

若干图的冠积的星染色

2020-08-20蔡瑾田双亮安卓莫

商情 2020年36期
关键词:拷贝顶点染色

蔡瑾 田双亮 安卓莫

【摘要】  图G的一个k-星染色σ是使G不存在4阶的2色路的k-点染色, 其中最小的k值称为G的星色数, 记为Xs(G)。 简单图G与H的冠积G·H被定义为将G的第i个顶点与第i个H的拷贝中每一个顶点连接得到的图. 主要研究了任意图G与H的冠积的星色数的上界及某些特殊图G与任意图H的冠积的星色数Xs(G·H), 具体结果为:Xs(G·H)≤Xs(G)+Xs(H) ; 当G为m阶路时, Xs(Pm·H)=Xs(H)+2; 当G为m+1解星时, Xs(K1,m·H)=Xs(H)+2; 当G为m≠5阶圈时,Xs(Cm·H)=Xs(H)+2 。

【关键词】冠积  星染色  路  星  圈

一、引言

本文所考虑的图都是有限无向的简单连通图,记(m)n=m(modn), 其中m为整数,n为整数。

图的点染色是图论中的重要内容,图的正常点染色仅要求任意两个相邻的顶点所染的颜色不同,对点染色的要求不同,就会有不同的染色形式. 随着对点染色的染色形式的广泛推广,提出了许多有意义的染色形式。图G的一个k-星染色σ是使G中不存在4阶的2色路的k-点染色, 其中最小的k值称为G的星色数,记为Xs(G), 该染色是由Grünbaum在文献[1]中提出来的. 这种染色方式在许多文章中被研究,如Vinve在文献[2]中推广了图的染色问题并以另一种形式引入了星染色的概念; Fertin等人在文献[3]中确定了特殊图的星色数的精确值以及部分图的星色数的界; Albertson等人在文献[4]中证明了平面图的星色数最多不超过20; Lyons在文献[5]中证明了图的无圈染色也是一个星染色,且给出了一个寻找图的最优星染色的线性算法。

在下文的討论中将用到如下引理1.1-1.3。

引理1.1 对于任意整数n≥3,当n≠5时,Xs(Cn)=3, 否则Xs(Cn)=4。

引理1.2 对于任意整数n,m≥2,Xs(Kn,m)=min{m,n}+1。

引理1.3 对于任意整数m≥3,Xs(Km)=m。

图的运算是研究图的构造的重要工具,其运算方式有许多, 常见的图的运算有冠积、直积、强积、半强积等,其中m阶图G和n阶图H的冠积G·H被定义为取G的1个拷贝, H的m个拷贝,并将G的第i个顶点与第i个H的每一个顶点连接得到的图, 这种运算方式是由Harary和Frucht于1970年在文献[6]中提出的。对于图的冠积运算研究有许多, 文献[7-13]都对不同图的冠积运算的性质进行了研究. 本文将对特殊图与任意图的冠积的星染色进行研究。

Venkatesan在文献[14]中分别给出了n阶路与n阶完全图, 阶圈,n+1阶星, n1+n2阶完+1全二部图及n=阶星与n阶完全图的星色数,其主要研究结果如下:

命题1.1 对于任意n≥2,Xs(Pn·Kn)=n+2.n

命题1.2 对于任意n≥3, 若n=5则Xs(Pn·Cn)=6; 否则,Xs(Pn·Cn)=5。

命题1.3 对于任意正整数n≥3,Xs(Pn·K1,n)=4。

命题1.4 对于任意n≥2且n=n1或n=n2,Xs(Pn·Kn1,n2)=min{n1+n2}+3。

命题1.5 对于任意n≥3,Xs(K1,n·Kn)=n+2。

文献[14]主要研究同阶特殊图的冠积的星色数,本文对其结果进行推广,分别得到了m阶路以及m+1阶星与任意简单图的星色数.同时又研究了m阶圈与任意简单图的星色数,并给出了对应的染色方法.

二、主要结果及其证明

设G和H是阶数分别为m,n的图,其中m,n≥2, 且Xs(H)=r。记G,H和G·H中H的每一个拷贝Hi的顶点集分别为V(G)={x0,x1,…,xm-1},V(H)={y0,y1,…,yn-1},V(Hi)={y■■,y■■,…,y■■},其中i=0,1,…,m-1。令H■■=K■■∨H■,其中V(H■■)={xi}∪V(Hi),V(K■■)={xi},则G·H的边集为E(G·H)=E(G)∪(∪■■E(H■■))。文中未说明的符号和术语见文献[14]。

关于两个图的星色数与他们的冠积的星色数之间的关系, 有以下定理2.1。

定理2.1 Xs(G·H)≤Xs(G)+Xs(H)。

证明 记Xs(G)=s。只需证明G·H存在一个(s+r)-星染色。现在,分两步构造G·H的一个星染色:首先,用s种颜色对G·H中G的拷贝进行星染色,该染色记为σ1; 其次,用另外r种新的颜色分别对G·H中H的每一个拷贝Hi进行星染色,该染色记为σ2。并将σ1与σ2合并,记为σ。显然,σ1是G·H的一个(s+r)-正常点染色。

现在证明G·H中不包含4阶的2色路。任取G·H中的一个4阶路P4,显然,要么|V(P4)∩V(G)|或4,要么1≤|V(P4)∩V(G)|≤3。对于前者,由于σ1与σ2是分别限制在G和H的拷贝上的星染色,则不P4是2色路;对于后者,因为σ1与σ2所用颜色不同,所以P4不是2色路。因此, Xs(G·H)≤Xs(G)+Xs(H)。

定理2.1的上界是可达的。如当G是星时定理中等号成立, 具体证明方法见定理2.2。为证明定理2.2,引入以下引理2.1。

引理2.1 Xs(P2·H)=Xs(H)+2。

证明 当G是2阶路P2时,令P2=x1x2。容易证明Xs(P2·H)≥r+2。假设Xs(P2·H)≤r+1且σ是P2·H的一个(r+1)-星染色,可以推出矛盾。设σ(x1)=α,σ(x2)=b显然,α≠b。由Xs(H)=r可知,H■■和H■■的顶点颜色数皆为r+1。此时,存在顶点y■■和y■■,使得σ(y■■)=b,σ(y■■)=α,其中k0,l0∈(0,1,…,n-1),则P2·H中存在4阶的2色路,与假设矛盾。

为证明Xs(P2·H)≤r+2, 分两步构造如下染色σ:首先,用2种颜色对P2·H中P2的拷贝进行染色;其次,用另外r种新的颜色分别对P2·H中每一个H的拷贝进行星染色。显然,σ是P2·H的一个(r+2)-星染色。

定理2.2 Xs(K1,m·H)=Xs(H)+2。

证明 当G是m+1阶星K1,m时,令K1,m的顶点集为{x0,x1,…,xm},其中x0是度为m的顶点,其它顶点度皆为1。由引理2.1可以证明Xs(K1,m·H)≥r+2。为证明Xs(K1,m·H)≤r+2,分两步构造如下染色σ:首先,用2种颜色对K1,m·H中K1,m的拷贝进行星染色;其次,用另外r种新的颜色分别对K1,m·H中每一个H的拷贝进行星染色。显然,σ是K1,m·H的一个(r+2)-星染色。

所以,Xs(K1,m·H)=Xs(H)+2。此时,Xs(G·H)=Xs(G)+Xs(H)。

定理2.2可以对命题1.5中结果进行如下推广: 对于任意整数m,n≥2,有Xs(K1,m·Kn)=n+2。

对于某些特殊图而言, 定理2.1中不等式严格成立。如G是路或圈时,Xs(G·H)=Xs(G)+Xs(H)-1,具体证明方法见定理2.3-2.4。

定理2.3 Xs(Pm·H)=Xs(H)+2。

证明 当G是m阶路Pm时,令Pm=x0x1…xm-1。由引理2.1可以证明Xs(Pm·H)≥r+2。为证明Xs(Pm·H)≤r+2,分两步构造如下染色σ首先,用颜色(i)r+2对Pm·H中Pm的拷贝的顶点xi染色,其中i=0,1,…,m-1;其次,用颜色集{(i+j)r+2|1≤j≤r}分别对Pm·H中每一个H的拷贝进行星染色。显然,σ是一个正常点染色。下面证明σ是一个星染色。

任取Pm·H中的4階路P4,当|V(P4)∩V(Pm)|=4或0时,显然,P4不是2色路; 当|V(P4)∩V(Pm)|=3时,由于Pm·H中Pm的拷贝的相继3个顶点颜色互不相同,显然,P4不是2色路; 当|V(P4)∩V(Pm)|=2时,P4有两个顶点要么在Pm·H中某一个H的拷贝Hi上, 要么在Pm·H中某2个H的拷贝Hi,Hj上。对于前者,由于σ(xi)=(i)r+2≠(i+k)r+2,其中,1≤k≤r则上至少有3个顶点颜色不同, 即P4不是2色路。对于后者,不妨假设j=i+1,此时,σ(xi)=(i)r+2,σ(xJ)=(i+1)r+2,在Hj上的任意顶点y■■的颜色为(i+k+1)r+2,其中1≤k≤r,显然,这3个顶点颜色互不相同,即P4不是2色路; 当|V(P4)∩V(Pm)|=1时,由于P4在Hi上的3个相继顶点颜色数至少为2,且xi的颜色与它们互不相同,则P4不是2色路。

所以,Xs(Pm·H)=Xs(H)+2。此时,Xs(G·H)=Xs(G)+Xs(H)-1

由定理2.3及引理1.1-1.3可以对命题1.1-1.4进行如下推广:对于任意整数m,n≥2,有Xs(Pm·Kn)=n+2;对于任意整数m≥2,n≥3,当n≠5时,Xs(Pm·Cn)=5; 对于任意整数m,n≥3,有Xs(Pm·K1,n)=4; 对于任意整数m,n1,n2≥2,有Xs(Pm·Kn1n2)=min{n1,n2}+3。

定理2.4 ,Xs(Cm·H)=Xs(H)+2其中m≠5。

证明 当G是m阶圈Cm时,令Cm=x0x1…xm-1x0。由引理2.1可以证明Xs(Cm·H)≥r+2。为证明Xs(Cm·H)≤r+2,分两步构造如下染色σ:首先,用颜色0,1,2对Cm·H中Cm的拷贝进行星染色,其染色方法同文献[3]中定理5; 其次,用颜色3,4,…,r+1和颜色(σ(xi)+1)3分别对Cm·H中H的每一个拷贝进行星染色。容易证明,σ是一个星染色。

所以,Xs(Cm·H)=Xs(H)+2(m≠5)。此时,Xs(G·H)=Xs(G)+Xs(H)-1。

参考文献:

[1] Grünbaum B. Acyclic Colorings of Planar Graphs [J]. Israel Journal of Mathematics, 1973, 14(4):390-408.

[2] Vince A. Star chromatic number [J]. Journal of Graph Theory, 1988, 12(4): 551-559.

[3] Fertin G , André R, Reed B . On Star Coloring of Graphs[C]. International Workshop on Graphtheoretic Concepts in Computer Science, OAI, 2001.

[4] Albertson M O , Chappell G G , Kierstead H A , et al. Coloring with no 2-Colored s [J].Electronic Journal of Combinatorics, 2004, 11(1).

[5] Lyons A . Acyclic and star colorings of cographs[J]. Discrete Applied Mathematics, 2011, 159(16):1842-1850.

[6] Frucht R , Harary F . On the corona of two graphs[J]. Aequationes Mathematicae, 1970, 4(1-2):264-264.

[7] Garcia V, Pedro. On the toughness of the corona of two graphs[J]. International Journal of Computer Mathemtics,2011, 88(13): 2697-2706.

[8] Kuziak D , Yero I G , Rodríguez-Velázquez, Juan A. On the strong metric dimension of corona product graphs and join graphs[J]. Discrete Applied Mathematics, 2013, 161(7-8):1022-1027.

[9] Tavakoli M , Rahbarnia F , Ashrafi A R . Studying the corona product of graphs under some graph invariants[J]. Transactions on Combinatorics, 2014.

[10] Abdo H , Dimitrov D . The irregularity of graphs under graph operations[J]. Discussiones Mathematicae Graph Theory, 2014, 34(2):263.

[11] Barragán-Ramírez G.A, Gómez C.G, Rodríguez-Velázquez J.A. Closed formulae for the local metric dimension if corona product graphs[J], Electronic Notes in Discrete Mathematics,2014,46(0): 27-34.

[12] Pattabiraman K , Kandan P . Weighted PI index of corona product of graphs[J]. Discrete Mathematics Algorithms and Applications, 2014, 06(04):1450055.

[13] Rodríguez-Velázquez, Juan A, Barragán-Ramírez, Gabriel A, García Gómez, Carlos. On the Local Metric Dimension of Corona Product Graphs[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2016, 39(1 Supplement):157-173.

[14] Venkatesan K , Vivin V , Mathiyazhagan V . On Star Coloring Of Corona Graphs[J]. Applied Mathematics E Notes, 2015:97-104.

基金项目: 西北民族大学科研创新团队计划资助,国家民委科研资助项目(14XBZ018)。

作者簡介: 蔡瑾(1997-), 女, 吉林人, 硕士研究生;田双亮(1965-), 男, 教授, 研究方向为图论及组合优化。

猜你喜欢

拷贝顶点染色
KAIHARA开发出加强环保型染色的方法
△(G)=8且不含有三角形,4—圈的平面图的完备染色
类比法在图染色中的应用
文化拷贝应该如何“拷”
两类图的b—染色数和研究
“图形的认识”复习专题
影子与我
删繁就简三秋树
数学问答
一个人在顶点