若干合成图的星全染色*

2012-08-18 03:27王晓琦田双亮
关键词:合成图种颜色顶点

王晓琦 田双亮

(西北民族大学数学与计算机科学学院 兰州 730030)

0 引 言

本文所考虑的图G均为有限无向简单图,用V(G),E(G)分别表示图G的点和边的集合.并用Δ(G)表示G的最大度.

定义1[1]简单图G和H 的合成图是指具有顶点集V(G)×V(H)的简单图G[H],它的顶点(u,v)和另一个顶点(u′,v′)相邻当且仅当或者uu′∈E(G),或者u=u′且vv′∈E(H).

合成图G[H]也可看成是若干个同构于H的不相交图关于G的等广义联图[2].特殊地,当G为n阶完全图Kn,合成图Kn[H]也可称为n阶完全图Kn与H 的等多重联图[3].

定义2 图G的k-全染色是从V(G)∪E(G)到S={1,2,…,k}的一个映射σ,使得G 中没有相邻顶点或边具有相同的像,且每个顶点与其关联边有不同的像.使G存在k-全染色的最小k值称为G的全色数,记为χT(G).

定义3 图G的一个k-全染色σ被称为k-星全染色,如果图G中任意长为2的路的顶点和边染不同颜色.即G中任意星上的顶点与边染不同的颜色.使G存在k-星全染色的最小的k值称为G的星全色数,记为χst(G).

由定义3,容易得到以下引理:

引理1 对任意n阶简单图G,n≥3,有2Δ(G)+1≤χst(G)≤n+χ′(G).式中:χ′(G)为G的边色数.

引理2 对G的任意子图H,有χst(H)≤χst(G).

引理3 若G的直径D(G)≤2,则在G的任一星全染色中,G的不同顶点必染不同的颜色.

在后面的讨论中,需用到以下引理:

引理4 偶图G的边色数等于Δ(G).

文献[2]研究了一些等广义联图(或合成图)的Mycielski图的星全染色,文献[4-7]研究了完全图与完全多部图的Mycielski图,以及轮,扇与路的广义Mycielski图的星全染色.本文将研究n+1阶轮,扇,星与m阶简单图的合成图的星全染色.文中未加说明的术语及符号可参见文献[1]和[4].

1 主要结果及其证明

设简单图G与H 的顶点集分别为V(G)={ui|i=0,1,…,n}与V(H)={vi|i=0,1,…,m-1}.在G[H]中,记wij=(ui,vj),并令Vi={(ui,vj)|j=0,1,…,m-1}.由合成图的定义,G[H]可表述为若干边不交的子图之并,即

式中:Gi,j为以(Vi,Vj)为二分类的完全偶图,Hi表示以Vi为顶点集且同构于H 的简单图.显然,在G[H]中,有Gi,j≅Km,m,且Hi与Hj是不相交的,其中i≠j,i,j=0,1,…,n.下面研究当G 为n+1阶轮Wn,扇Fn,或星Sn,且H 为m 阶特殊图时合成图G[H]的星全染色.

设n+1阶轮Wn的顶点集与边集分别为

其中ui+1的下标取模n,n≥4.

显然,n+1阶扇Fn与星Sn可由Wn删去若干条边得到.

引理5 设G为n阶简单图,n≥5.若Δ(G)=2,则G存在n-星全染色,使得G的不同顶点染不同的颜色.

证明 不妨假设G是简单连通图.因Δ(G)=2,所以G为n阶圈或路.仅证明当G为n阶圈时引理结论成立,当G为n阶路时,可类似证明.

设G为n 阶圈且G=v0e0v1e1…vn-1en-1v0.设颜色集合为S={0,1,…,n-1}.现在定义如下一个从V(G)∪E(G)到S的映射σ:

显然σ为G的n-星全染色,且使得G的不同顶点染不同色.因此,引理结论成立.

定理1 设G为n+1阶轮,扇,或星,且H为m 阶简单图,其中n≥4,m≥5.若Δ(H)=2,则χst(G[H])=(2n+1)m.

证明 记G*=G[H].显然,G*的直径不超过2,即D(G*)≤2.由引理3,在G*的任一星全染色中,G*的不同顶点必染不同的颜色,又因|V(G*)|=(n+1)m,所以至少需要(n+1)m 种颜色.另一方面,对任意边uv∈E(Gn,i),i=0,1,…,n-1,每一顶点ω∈V(G*)\{u,v}均与u或v相邻,所以在G*的星全染色σ中,的每一边不能与G*的任一顶点染相同的颜色.又因为是最大度为mn 的偶图,由引理4知,)=mn.所以,χst(G*)≥(n+1)m+mn=(2n+1)m.又因为Sn⊂Fn⊂Wn,由引理2,χst(Sn[H])≤χst(Fn[H]≤χST(Wn[H]).因此,欲证χst(G[H])≤2(n+1)m,仅需证明当G*=Wn[H]时,G*存在(2n+1)m-星全染色.

设颜色集合为S=A∪B,且|S|=(2n+1)m,|A|= (n+1)m,|B|=nm.其中:A =;B =;|Ai|=m;|Bj|=m.现在分3步构造G*的染色σ:在式(1)中,首先用Ai中的m种颜色对Hi进行顶点染色,使得不同顶点染不同色,i=0,1,…,n.其次,对i=0,1,…,n,因为Hi≅H及Δ(H)=2,由引理5,可用Hi的顶点颜色对Hi的边进行染色,使其成为Hi的m-星全染色.最后,用B中mn种颜色对∪uiuj∈E(G)Gi,j进行正常边染色.具体地,因为Gi,j≅Km,m,由引理4,可用Bi中的m 种颜色对Gn,i进行正常边染色,用Bi+2中的m种颜色对Gi,i+1进行正常边染色,其中Bi+2的下标与Gi,i+1的第二个下标i+1取模n,其中i=0,1,…,n-1.

容易看出,以上染色σ是G*的(2n+1)m-全染色,且在σ中,∪uiuj∈E(G)Gi,j的每一边所染颜色与任意顶点所染颜色均不相同,并满足G*的不同顶点染不同的颜色.同时,σ限制在每一个Hi上均为Hi的星全染色,且不同的Hi所用的颜色集合不同.又因Hi与Hj是不相交的,其中i≠j,i,j=0,1,…,n,所以在σ中,G*的任意长为2的路的顶点和边均染不同颜色,即σ是G*的(2n+1)m- 星全染色.因此,χst(G*)= (2n+1)m.

定理2 设G为n+1阶轮,扇,或星,若H满足χ′(H)=Δ(H)=m-1,其中n,m≥4,则χst(G[H])=2(n+1)m-1.

证明 记G*=G[H].由已知及引理1可得

由上式可知,若能证明χ′(G*)≤(n+1)m-1,则定理结论成立.又因Sn⊂Fn⊂Wn,由合成图的定义,有G*⊆Wn[H].因此,仅需证明当G=Wn时,G*存在((n+1)m-1)-正常边染色.

假设G=Wn,并设颜色集合S=B∪C,且|S|=(n+1)m-1,|B|=mn,|C|=m-1,其中B=,且|Bj|=m,j=0,1,…,n-1.

现在构造G*的边染色σ:在式(1)中,首先用B中的nm 种颜色对 ∪uiuj∈E(G)Gij进行正常边染色,染色方法与定理1证明中的第三步相同.其次,因χ′(H)=m-1,所以可用C中的m-1种颜色对每一个Hi进行正常边染色.

显然,以上染色σ是G*的((n+1)m-1)-正常边染色.因此,定理结论成立.

2 结 论

由定理2可直接得到以下结论:设G为n+1阶轮,扇,或星,其中n≥4.若H满足以下条件之一:(1)H 为m 阶轮,扇,或星,其中m≥4;(2)H为偶阶完全图,则χst(G[H])=2(n+1)m-1.

[1]BONDY J A,MURTY U S R.Graph theory with application[M].New York:American Elsevier,1976.

[2]田双亮.等广义联图的Mycielski图的星全染色[J].山东大学学报:理学版,2009,45(6):23-26,34.

[3]田双亮,陈 萍.若干多重联图的边染色[J].南开大学学报:自然科学版,2007,40(3):27-30.

[4]YAP H P.Total colorings of graphs[M].New York:Springer Verlag,1996.

[5]李沐春,强会英,张忠辅.完全图和完全多部图的Mycielski图的星全染色[J].福州大学学报:自然科学版,2009,37(2):180-183.

[6]强会英,李沐春,徐保根,等.轮和路的广义Mycielski图的星全染色[J].兰州理工大学学报,2008,34(4):145-147.

[7]强会英,李沐春,张忠辅.星图和扇图的广义Mycielski图的星全染色[J].江西师范大学学报:自然科学版,2009,33(3):306-308.

猜你喜欢
合成图种颜色顶点
沉睡的船
过非等腰锐角三角形顶点和垂心的圆的性质及应用(下)
过非等腰锐角三角形顶点和垂心的圆的性质及应用(上)
“月全食”+“超级月亮”
观察:颜色数一数
对“地球的运动”中的一些教学浅谈
迷人的颜色
数学问答
新鲜闻
一个人在顶点