特殊图的广义字典积的邻点可区别全染色

赵晓翠，田双亮，何雪，焉秋瑶

（西北民族大学数学与计算机科学学院，甘肃兰州730030）

特殊图的广义字典积的邻点可区别全染色

赵晓翠，田双亮，何雪，焉秋瑶

（西北民族大学数学与计算机科学学院，甘肃兰州730030）

设G是具有顶点集V（G）＝{t0，…，tn-1}（n≥2）的图，hn=（Hi）i∈{0,1，…，n-1}是不相交图的序列，其中Hi的顶点集为V（Hi）={（ti，y1)，…，（ti，yx)}，x≥1。称G[hn]为G与hn=（Hi）i∈{0,1，…，n-1}的广义字典积，其中G[hn]的顶点集为，且两个顶点（ti，yp)与（tj，yq)相邻当且仅当ti=tj且（ti，yp)（ti，yq)∈E（Hi），或（ti，tj）∈E（G）。研究了一些广义字典积G[hn]的邻点可区别全染色，其中G表示n≥6阶轮，扇或星。

广义字典积；邻点可区别全染色；邻点可区别全色数

1 知识准备

笔者所考虑的图G都是有限无向的简单图，用V（G），E（G）分别表示G的点和边的集合。并用Δ（G）与D（G）分别表示G的最大度与直径。

定义1[1]设G是具有顶点集V（G）＝{t1，t2，…，tn}，n≥2的图，hn=（Hi）i∈{1，2，…，n}是不相交图的序列，其中图Hi的顶点集V（Hi）={（ti，y1)，（ti，y2)，…，（ti，yx)}，x≥1。称G[hn]为G与hn=（Hi）i∈{1，2，…，n}的广义字典积，其中G[hn]的顶点集为，且两个顶点（ti，yp)与（tj，yq)相邻当且仅当ti=tj且（ti，yp)（ti，yq)∈E（Hi），或titj∈ E（G），若Hi≌H，则G[hn]记为G[H]，且称G[H]为G与H的字典积。

由定义1，两个图G1与G2的联图[2]G1∨G2可看成P2[h2]，其中h2=（Gi）i∈{1，2}。G与hn=（Hi）i∈{1，2，…，n}的广义字典积G[hn]也可称为不相交图H1，H2，…，Hn关于G的广义联图[3]。等广义联图G（n，H）为n阶图G与H的字典积G[H]。完全多部图可看成是完全图与若干零图（完全图的补图）序列的广义字典积，如每部分有m个顶点的等完全n-部图K（n，m）是n阶完全图Kn与m阶完全图的补图Km的字典积图。多重联图[4]K（G1，G2，…，Gn）则可看成是n阶完全图Kn与hn=（Gi）i∈{1，2，…，n}的广义字典积。

定义2[5]设G是阶至少为2的连通图，k是正整数且σ是一从V（G）∪E（G）到{1,2，…，k}的映射。对任意u∈V（G），用C（u）表示{σ（u）}∪{σ（uv）|uv∈E（G）}。如果：

（1）对任意uv，vw∈E（G），u≠w，有σ（uv）≠σ（vw）；

（2）对任意uv∈E（G），有σ（u）≠σ（v），σ（u）≠σ（uv），σ（v）≠σ（uv），则称σ是G的k-正常全染色。若σ是G的k-正常全染色，且

（3）对任意uv∈E（G），有C（u）≠C（v），则称σ是G的一k-邻点可区别全染色（简记为k-AVDTC）。且称χat（G）=min{k|G存在k-AVDTC}为G的邻点可区别全色数。

定义2中C(u)称为点u在σ下的色集合,C(u)在全体颜色构成的集合C={1,2,…，k}中的补集记为。

对阶至少为2的简单连通图G，χat（G）显然存在。

由定义2，容易得到以下引理：

引理1如果图G有两个相邻的最大度点，则χat（G）≥Δ（G）+2，其中Δ（G）为G的最大度。

Burris与Schelp在文献[6]中提出了关于图的点可区别边染色猜想：对没有孤立边且至多含有一个孤立顶点的n阶图G，有χ′vd（G）≤n+1，其中χ′vd（G）表示G的点可区别边色数。Cristina Bazgan等在文献[7]中证明了该猜想正确。由此结果可知，n≥3阶简单连通图G与平凡图K1（仅含一个顶点的图）的联图的点可区别边色数不超过n+2，将G的每一顶点染成该顶点与K1的顶点连边所染颜色，并删去K1的顶点，则可得到G的一个（n+2）-邻点可区别全染色。因此，有以下引理：

引理2对n≥3阶简单连通图G，有χat（G）≤n+2。

在以后的讨论中要用到以下引理：

引理3[8]对n阶完全图Kn，有。其中χT（Kn）为Kn的全色数。

引理4[5]对n阶完全图Kn，n≥2，有。

引理5[5]对n阶完全图Cn，n≥4，有χat（Cn）=4。

文献[5]给出了圈、完全图、完全二部图、扇、轮和树的邻点可区别全色数。文献[9]给出了圈与扇的联图，得到了在不同取值情况下的邻点可区别全色数。文献[10]给出了几类特殊图的邻点可区别全色数。文献[11]得到了两条路的联图的邻点可区别全色数。笔者将研究广义字典积G[hn]中G为n阶轮，扇或星时的邻点可区别全染色。文中未加说明的术语及符号可参见文献[2]和文献[8]。

2 主要结果

下面研究当G为n阶轮，扇或星时，G与hn=（Hi）i∈{0,1，…，n-1}的广义字典积G[hn]的邻点可区别全染色，其中Hi为m阶简单图，i=0,1,…,n-1且n≥6，m≥3。

设n阶轮Wn的顶点集和边集分别为V（Wn）＝{t0，t1，…，tn-1}，E（Wn）＝{tn-1tj|j=0,1,…,n-2}∪{t0t1，t1t2，…，tn-3tn-2，tn-2t0}。n阶扇Fn与星Sn分别可由轮Wn删去一些边得到。为叙述方便，令V（Hi）={（ti，yj)|j=1,2,…,m}，并记vij=（ti，yj)。在G[hn]中，用Gkl表示具有二分类（V（Hk），V（Hl）)的m-正则二部图。

若G是n阶的轮即G=Wn，由图的广义字典积的定义，可将图G[hn]分解为三个边不交子图G（1），G（2）与G（3），即其中，G（3）=G01∪G12∪…∪Gn-3，n-2∪Gn-2，0。

定理1若Hn-1为空图，则χat（G[hn]）=（n-1）m+1。

证明假设G=Wn。情形G=Fn与G=Sn的证明过程类似。记G*=G[hn]。因χat（G*）≥Δ（G*）+1=（n-1）m+1。欲证χat（G*）≤（n-1）m+1，仅需给出G*的一个（（n-1）m+1）-AVDTC。

首先，对G（2）进行边染色。用Ai中的m种颜色对m-正则二部图Gn-1，i进行正常边染色，i=1,2,…,n-1。

其次，对G（3）进行边染色。用Ai+3（下标i+3取模n-1）中的m种颜色对m-正则二部图Gij进行正常边染色，i=0,1,…,n-2。

最后，对G（1）进行邻点可区别全染色。具体地，用An-1中的一种颜色对Hn-1的顶点进行染色；由引理2，用Ai+1∪{ai+4，0，ai+4，1}（下标i+1与i+4均取模n-1）中的m+2种颜色对Hi进行邻点可区别全染色，使得Hi的顶点不染颜色ai+4，0与ai+4，1，i=0,1,…,n-2。

显然，以上染色σ是G[hn]的一个（（n-1）m+1）-正常全染色，且Hi中的任意相邻顶点在σ下有不同的色集合，其中i=0,1,…,n-1。因当n≥6时，对i=0,1,…,n-2，Hn-1的顶点与Hi的顶点的度数不相等，所以它们在σ下有不同的色集。因Hi的每一顶点在σ下的色集合必包含Ai∪Ai+2∪Ai+3，但对任意i≠j，Hj的每一顶点在σ下的色集合至少不含Ai∪Ai+2∪Ai+3中的一种颜色，i，j=0,1,…,n-2，因此，所构造染色σ是G[hn]的一个（（n-1）m+1）-邻点可区别全染色，即χat（G[hn]）≤（n-1）m+1。故定理结论成立。

定理2若Hn-1为完全图，则χat（G[hn]）=nm+1。

证明假设G=Wn。情形G=Fn与G=Sn的证明过程类似。记G*=G[hn]。因G*的最大度为nm-1且最大度点相邻，由引理1，χat（G*）≥Δ（G*）+2=nm+1。欲证χat（G*）≤nm+1，仅需给出G*的一个（nm+1）-AVDTC。

情况1m是奇数。由（1）式知，可分三步对G*进行全染色。

首先，对G（2）进行边染色。用Ai中的m种颜色对m-正则二部图Gn-1，i进行正常边染色，i=1,2,…,n-2；用A0∪An中的m+1种颜色对Gn-1，0进行如下边染色：当i+j≠m+1时，令f（vn-1，iv0j）=a0，i+j-1（mod n+1），i，j=0,1,…, m-1；当i+j=m+1时，令f（vn-1，iv0j）=b，i，j=0,1,…,m-1。

其次，对G（3）进行边染色。用Ai+3（下标i+3取模n-1）中的m种颜色对m-正则二部图Gij进行正常边染色，i=0,1,…,n-2。

最后，对G（1）进行邻点可区别全染色。具体地，由引理3，用An-1中的m种颜色对Hn-1进行正常全染色；由引理2，用Ai+1∪{an-1，0，an-1，1}（下标i+1取模n-1）中的m+2种颜色对Hi进行邻点可区别全染色，使得Hi的顶点不染颜色an-1，0与an-1，1，i=0,1,…,n-2。

显然，以上染色σ是G[hn]的一个（nm+1）-正常全染色，类似于定理1证明中的讨论，所构造染色σ是G[hn]的一个（nm+1）-邻点可区别全染色，即χat（G[hn]）≤nm+1。故定理结论成立。

情况2m是偶数。与情况1类似，可分三步对G*进行全染色。

首先，对G（2）进行边染色。用Ai中的m种颜色对m-正则二部图Gn-1，i进行正常边染色，i=1,2,…,n-1。

其次，对G（3）进行边染色。用Ai+3（下标i+3取模n-1）中的m种颜色对m-正则二部图Gij进行正常边染色，i=0,1,…,n-2。

最后，对G（1）进行邻点可区别全染色。具体地，由引理4，用An-1∪An中的m+1种颜色对Hn-1进行点可区别全染色；由引理2，用Ai+1∪{an-1，0，an-1，1}（下标i+1取模n-1）中的m+2种颜色对Hi进行邻点可区别全染色，使得Hi的顶点不染颜色an-1，0与an-1，1，i=0,1,…,n-2。

显然，以上染色σ是G[hn]的一个（nm+1）-正常全染色，类似于定理1证明中的讨论，所构造染色σ是G[hn]的一个（nm+1）-邻点可区别全染色，即χat（G[hn]）≤nm+1。故定理结论成立。

定理3若Hn-1为圈，则χat（G[hn]）＝（n-1）m+4。

假设G=Wn。情形G=Fn与G=Sn的证明过程类似。记G*=G[hn]。因G*的最大度为（n-1）m+2且最大度点相邻，由引理1，χat（G*）≥Δ（G*）+2=（n-1）m+4。欲证χat（G*）≤（n-1）m+4，仅需给出G*的一个（（n-1）m+4）-AVDTC。

显然，以上染色σ是G[hn]的一个（（n-1）m+4）-正常全染色，类似于定理1证明中的讨论，所构造染色σ是G[hn]的一个（（n-1）m+4）-邻点可区别全染色，即χat（G[hn]）≤（n-1）m+4。故定理结论成立。

定理4若Hn-1为轮，扇或星，则χat（G[hn]）＝nm。

证明设G=Wn。情形G=Fn与G=Sn的证明过程类似。记G*=G[hn]。因G*的最大度为nm-1，所以χat（G*）≥Δ（G*）+1=nm。欲证χat（G*）≤nm，仅需给出G*的一个（nm）-AVDTC。

显然，以上染色σ是G[hn]的一个（nm）-正常全染色，类似于定理1证明中的讨论，所构造染色σ是G[hn]的一个（nm）-邻点可区别全染色，即χat（G[hn]）≤nm。故定理结论成立。

[1]Waldemar Szumny，Iwona Wloch，Andrzej Wloch．On the existance and on the number of（k，l）-kernels in the lexicographic product of graphs[J]．Discrete Mathematics，2008，308：4616-4624．

[2]Bondy J A，Murty U S R．Graph Theory with Application[M]．New York：Macmillan Press Ltd，1976．

[3]Tian Shuangliang．Star total colorings of mycielski’s graphs of balanced general join of graph[J]．Journal of Shandong University（Natural Science），2009，45（6）：23-26，34．

[4]田双亮，陈萍．若干多重联图的边染色[J]．南开大学学报：自然科学版，2007，40（3）：27-30．

[5]张忠辅，陈祥恩，李敬文，等．关于图的邻点可区别全染色[J]．中国科学A辑，2004，34（5）：574-583．

[6]Burris A C，Schelp R H．Vertex-distinguishing proper edge colorings[J]．Journal of Graph Theory，1997，26：73-82．

[7]Bazgan C，Harkat-Benhamdine A，Hao Li，et al．On theVertex-distinguishing proper edge colorings of graphs[J]．Journal of Combinatorial Theory，1999，75：288-301．

[8]Yap H P．Total Colourings of Graphs[M]．New York：Springer-Verlag，1996．

[9]马刚，张炜，张忠辅．图Cm∨Fn的邻点可区别全染色[J]．西北民族大学学报：自然科学版，2005，26（2）：24－29．

[10]董海燕，孙磊，孙艳丽．关于邻点可区别全染色的几个新结果[J]．广西师范大学学报：自然科学版，2005，23（3）：41－43．

[11]陈祥恩，张忠辅．Pm∨Pn的邻点可区别全染色[J]．西北师范大学学报：自然科学版，2005，41（1）：13－15．

Adjacent vertex distinguishing total coloring of the generalized lexicographic product of special graphs

ZHAO Xiaocui，TIAN Shuangliang，HE Xue，YAN Qiuyao
（School of Mathematics and Computer Science，Northwest University for Nationalities，Lanzhou 730030，China）

Let G be a graph on V（G）＝{t0，…，tn-1}（n≥2）and hn=（Hi）i∈{0,1，…，n-1}be a sequence of vertex disjoint graphs on V（Hi）={（ti，y1)，…，（ti，yx)}，x≥1．By the generalized lexicographic product of G and hn=（Hi）i∈{0,1，…，n-1}we mean the graph G[hn]such that，and two distinct vertices（ti，yp)and（tj，yq)are adjacent if and only if ti=tjand（ti，yp)（ti，yq)∈E（Hi），or（ti，tj）∈E（G）．In this paper，we have studied adjacent vertex distinguishing total coloring of the generalized lexicographic product G[hn]of special graphs，where G is an wheel，a fan or a star with n≥6 vertices．

generalized lexicographic product；adjacent vertex distinguishing total coloring；adjacent vertex distinguishing total chromatic number

O157.5MR（2000）Subject Classification：05C15

A

1672－0687（2015）01－0016－04

责任编辑：谢金春

2013－09－06

国家自然科学基金资助项目（11161041）；国家民委科研资助项目（10XB01）；中央高校基本科研业务费专项资金项目（zyz2012089）；西北民族大学中央高校科研专项资金资助研究生项目（ycx13160）；西北民族大学中央高校科研专项资金资助研究生项目（ycx13163）

赵晓翠（1989-），女，陕西韩城人，硕士研究生，研究方向：图论及组合优化。