圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

苗 婷 婷,王 治 文,陈 祥 恩*

(1.西北师范大学 数学与统计学院， 甘肃 兰州 730070；2.宁夏大学 数学计算机科学学院， 宁夏 银川 750021 )

圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

苗 婷 婷1,王 治 文2,陈 祥 恩*1

(1.西北师范大学 数学与统计学院， 甘肃 兰州 730070；2.宁夏大学 数学计算机科学学院， 宁夏 银川 750021 )

一个图G的Ⅰ-全染色是指若干种颜色对图G的全体顶点及边的一个分配使得任意两个相邻点及任意两条相邻边被分配到不同颜色．图G的Ⅵ-全染色是指若干种颜色对图G的全体顶点及边的一个分配使得任意两条相邻边被分配到不同颜色．对图G的一个Ⅰ(Ⅵ)-全染色及图G的任意一个顶点x，用C(x)表示顶点x的颜色及x的关联边的颜色构成的集合(非多重集)．如果f是图G的使用k种颜色的一个Ⅰ(Ⅵ)-全染色，并且∀u，v∈V(G)，u≠v，有C(u)≠C(v)，则称f为图G的k-点可区别Ⅰ(Ⅵ)-全染色，或k-VDITC(VDVITC)．图G的点可区别Ⅰ(Ⅵ)-全染色所需最少颜色数目，称为图G的点可区别Ⅰ(Ⅵ)-全色数．利用组合分析法及构造具体染色的方法，讨论了圈与路的联图Cm∨Pn的点可区别Ⅰ(Ⅵ)-全染色问题，确定了这类图的点可区别Ⅰ(Ⅵ)-全色数，同时说明了VDITC猜想和VDVITC猜想对于这类图是成立的．

Ⅰ-全染色；点可区别Ⅰ-全染色；点可区别Ⅰ-全色数；圈与路的联

0 引 言

点可区别正常边染色、点可区别一般边染色以及点可区别正常全染色分别在文献[1-2]、[3-5]和[6-7]中被研究．文献[8]讨论了两类点可区别的未必正常的全染色：点可区别Ⅰ-全染色和点可区别Ⅵ-全染色．本文在文献[8]的基础上讨论圈与路的联图Cm∨Pn的点可区别Ⅰ-全染色和点可区别Ⅵ-全染色问题，确定这类图的点可区别Ⅰ-全色数和点可区别Ⅵ-全色数，且证明VDITC猜想和VDVITC猜想对Cm∨Pn是成立的．

1 准备工作

所谓图G的全染色是指若干种颜色对于图G的点及边的一个分配．

对于图G的一个全染色，如果任意两个相邻点有不同颜色，并且任意两条相邻边有不同颜色，那么称它为图G的Ⅰ-全染色．

对于图G的一个全染色，如果任意两条相邻边有不同颜色，那么称它为图G的Ⅵ-全染色．

χⅠvt(G),

χⅠvt(G)=min{k|G

如果f是图G的使用颜色1，2，…，k的一个Ⅰ-全染色，并且∀u，v∈V(G)，u≠v，有C(u)≠C(v)，则称f为图G的k-点可区别Ⅰ-全染色，或k-VDITC．图G的点可区别Ⅰ-全染色所需最少颜色数目，称为图G的点可区别Ⅰ-全色数，记为即有k-VDITC}．

χⅥvt(G),

χⅥvt(G)=min{k|G

如果f是图G的使用颜色1，2，…，k的一个Ⅵ-全染色，并且∀u，v∈V(G)，u≠v，有C(u)≠C(v)，则称f为图G的k-点可区别Ⅵ-全染色，或k-VDVITC．图G的点可区别Ⅵ-全染色所需最少颜色数目，称为图G的点可区别Ⅵ-全色数，记为即有k-VDVITC}．

)χⅠvt(G)=ζ(G)

猜想1[8](VDITC猜想或ζ(G)+1．

)χⅥvt(G)=ζ(G)

猜想2[8](VDVITC猜想或ζ(G)+1．

引理1 对于任意图G，如果存在两个Δ(最大度)顶点，则

χⅠvt(G)≥Δ+1.

引理

2[8]χⅠvt(G)≥ζ(G).

命题

1ζ(G)≤χⅥvt(G)≤χⅠvt(G).

假设p∈Z，而q为正整数，用(p)q表示{1，2，…，q}中的模q同余于p的那个数，即(p)q∈{1，2，…，q}且(p)q≡p(modq)．

令V(Cm∨Pn)={u1，…，um，v1，…，vn}，E(Cm∨Pn)={u1u2，u2u3，…，um-1um，umu1，v1v2，v2v3，…，vn-1vn}∪{uivj|i=1，2，…，m；j=1，2，…，n}．

2 主要结果

定理1 设Cm∨Pn是圈Cm和路Pn的联，m>n≥2，则

χⅠvt(Cm∨Pn)=m+2,n=2,3;m+3,n≥4.{

证明 当n=2，m=3时，C3∨P2有5个m+1度的点，有5-VDITCf，其染色方式很容易得到．

,χⅠvt(Cm∨P2)≥m+2,

当n=2，m≥4时，Cm∨P2有两个m+1度的点，m个4度点，由引理1知只需给出Cm∨P2的一个(m+2)-点可区别Ⅰ-全染色f．令

f(uivj)=i+j，f(uivj)∈{2，…,m+2}， 1≤i≤m，j=1，2；f(uiui+1)=i，i∈{2，…，m-1}；f(u1u2)=m+2，f(umu1)=1，f(v1v2)=1,f(v1)=1，f(v2)=3，f(u1)=2;f(ui)=i+2，i∈{2，…，m}

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(v1)={1，2，3，…，m+1}，C(v2)={1，3，4，…，m+1，m+2}；C(ui)={i-1，i，i+1，i+2}，i∈{3，…，m-1}；C(u1)={1，2，3，m+2}，C(u2)={2，3，4，m+2}，C(um)={m-1，m+1，m+2，1}

可见m+2个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

当n=3，m=4时，C4∨P3有1个m+2度的点，有6-VDITCf，当n=3，m=5时，C5∨P3有1个m+2度的点，有7-VDITCf，它们的染色方式容易得到，文中不详细写出．

χⅠvt(Cm∨P3)≥Δ(Cm∨P3)=m+2.

f(uivj)=(i+j)m+2，f(uivj)∈{1，…，m+2}，1≤i≤m，j=1，2，3；f(uiui+1)=i，i∈{1，2，…，m-1}，f(umu1)=m，f(v1v2)=1，f(v2v3)=2；f(v1)=1，f(v2)=2，f(v3)=4，f(u1)=3，f(um)=m+1，f(ui)=i+3，i∈{2，…，m-1}

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(v1)={1，2，3，…，m+1}，C(v2)={1，2，3，…，m+1，m+2}，C(v3)={1，2，4，5，…，m+1，m+2}；C(ui)={i-1，i，i+1，i+2，i+3}，i∈{2，…，m-1}，C(u1)={1，2，3，4，m}，C(um)={m-1，m，m+1，m+2，1}

可见m+3个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

当n≥4时有以下两种情形需要考虑．

情形1m≥n+2

χⅠvt(Cm∨Pn)≥ζ(Cm∨Pn)=m+3.

f(uivj)=(i+j)m+1，f(uivj)∈{1，2，…，m+1}，1≤i≤m，1≤j≤n；

f(vjvj+1)=m+2，j∈{1，2，…，n-1}，且j是奇数；f(vjvj+1)=m+3，j∈{1，2，…，n-1}，且j是偶数

f(uiui+1)=(i-1)m+1，i∈{1，2，…，m-1}；f(umu1)=m

f(ui)=i+1，f(ui)∈{2，…，m+1}，1≤i≤m

f(vj)=m+2，j∈{1，2，…，n}，且j是奇数；f(vj)=m+3，j∈{1，2，…，n}，且j是偶数

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(ui)={i+1，(i+2)m+1，…，(i+n)m+1，i-1，(i-2)m+1}，i≠1，m；C(u1)={2，3，…，n+1，m+1，m}，C(um)={m+1，1，2，…，n-1，m-2，m}，C(vj)={j+1，(j+2)m+1，…，(j+m)m+1，m+2，m+3}，j≠1；C(v1)={2，3，…，m+1，m+2}

可见m+n个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

情形2m=n+1

χⅠvt(Cm∨Pn)≥ζ(Cm∨Pn)=m+3.

f(uivj)=(i+j)m+1，f(uivj)∈{1，2，…，m+1}，1≤i≤m，1≤j≤n；

f(uiui+1)=m+2，i∈{2，3，…，m-1}，且i是奇数；f(uiui+1)=m+3，i∈{2，3，…，m-1}，且i是偶数；当m是偶数时，f(umu1)=m+3，f(u1u2)=m+2；当m是奇数时，f(umu1)=m+2，f(u1u2)=1

f(vjvj+1)=m+2，j∈{1，2，…，n-1}，且j是奇数；f(vjvj+1)=m+3，j∈{1，2，…，n-1}，且j是偶数

f(ui)=i+1，f(ui)∈{2，…，m+1}，1≤i≤m

f(vj)=m+2，j∈{1，2，…，n}，且j是奇数；f(vj)=m+3，j∈{1，2，…，n}，且j是偶数

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(ui)={i+1，(i+2)m+1，…，(i+n)m+1，m+2，m+3}，i≠1，2；当m为偶数时，C(u1)={2，3，…，m，m+2，m+3}，C(u2)={3，4，…，m+1，m+2，m+3}；当m为奇数时，C(u1)={2，3，…，m，m+2，1}，C(u2)={3，4，…，m+1，m+3，1}；C(vj)={j+1，(j+2)m+1，…，(j+m)m+1，m+2，m+3}，j≠1；C(v1)={2，3，…，m+1，m+2}

可见m+n个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

定理2 设Cm∨Pn是圈Cm和路Pn的联，n>m≥3，则

χⅠvt(Cm∨Pn)=n+3.

χⅠvt(Cm∨Pn)≥ζ(Cm∨Pn)=n+3.

情形1m≡0(mod 2)．令

f(uivj)=(i+j-1)n+1，f(uivj)∈{1，2，…，n+1}，1≤i≤m，1≤j≤n

f(vjvj+1)=n+2，j∈{1，2，…，n-1}，且j是奇数；f(vjvj+1)=n+3，j∈{1，2，…，n-1}，且j是偶数

f(uiui+1)=n+2，i∈{1，2，…，m-1}，且i是奇数；f(uiui+1)=n+3，i∈{1，2，…，m-1}，且i是偶数；f(umu1)=n+3

f(ui)=i，f(ui)∈{1，2，…，m}，1≤i≤m

f(vj)=n+2，j∈{1，2，…，n}，且j是奇数；f(vj)=n+3，j∈{1，2，…，n}，且j是偶数

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(ui)={i，i+1，(i+2)n+1，…，(i+n-1)n+1，n+2，n+3}，1≤i≤m；C(vj)={j，j+1，(j+2)n+1，…，(j+m-1)n+1，n+2，n+3}，j≠1；C(v1)={1，2，3，…，m，n+2}

可见m+n个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

情形2m≡1(mod 2)．令

f(uivj)=(i+j-1)n+1，f(uivj)∈{1，2，…，n+1}，1≤i≤m-1，1≤j≤n；f(umvj)=(i+j+2)n+2，1≤j≤n

f(vjvj+1)=n+3，j∈{1，2，…，n-1}，且j是奇数；f(vjvj+1)=n+2，j∈{1，2，…，n-1}，且j是偶数

f(uiui+1)=n+2，i∈{1，2，…，m-1}，且i是奇数；f(uiui+1)=n+3，i∈{1，2，…，m-1}，且i是偶数；f(umu1)=n+1

f(ui)=i，f(ui)∈{1，2，…，m}，1≤i≤m

f(vj)=n+3，j∈{1，2，…，n}，且j是奇数；f(vj)=n+2，j∈{1，2，…，n}，且j是偶数

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(ui)={i，i+1，(i+2)n+1，…，(i+n-1)n+1，n+2，n+3}，i≠1，m；C(u1)={1，2，…，n，n+1，n+2}，C(um)={1，2，…，n-1，n+1，n+2，n+3}；C(vj)={j，j+1，(j+2)n+1，…，(j+m-2)n+1，j-1，n+2，n+3}，j≠1；C(v1)={1，2，…，m-1，n+2，n+3}

可见m+n个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

因此，不管哪种情形所得到的染色f都是Cm∨Pn的一个VDITC．

定理3 设Cn∨Pn是路Cn和圈Pn的联，n≥3，则

χⅠvt(Cn∨Pn)=n+3,n=3,4;n+4,n≥5.{

C3∨P3、C4∨P4的VDITC很容易得到，文中略去．

当n=5时

,χⅠvt(C5∨P5)≥n+3=8.

χⅠvt(C5∨P5)≥9,

故且C5∨P5的一个9-VDITC很容易得到，文中不详细给出．

当n=6时

,χⅠvt(C6∨P6)≥n+3=9.

χⅠvt(C6∨P6)≥10.

故下面给出C6∨P6的一个10-VDITCf．令

f(uivj)=(i+j)10，f(uivj)∈{1，2，…，10}，1≤i≤6，1≤j≤6；f(u5v6)=3

f(uiui+1)=(i-1)10，i∈{1，2，…，5}，f(u6u1)=1；f(vjvj+1)=j，j∈{1，2，…，5}

点ui与vj染其关联边的颜色，其中ui染偶数色，vj染奇数色，并且相邻点着不同色．特别地，f(v5)=1．

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(ui)={(i-2)10，i-1，i+1，(i+2)10，…，(i+6)10}，i∈{2，…，5}；C(u1)={1，2，…，7，10}，C(u6)={1，2，3，4，7，8，9，10}，C(vj)={j-1，j，j+1，(j+2)10，…，(j+6)10}，j∈{2，3，4}；C(v1)={1，2，3，…，6，7}，C(v5)={1，3，4，…，10}，C(v6)={1，2，5，7，…，10}

可见12个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

χⅠvt(Cn∨Pn)≥ζ(Cn∨Pn)=n+4.

f(uivj)=(i+j-1)n+1，f(uivj)∈{1，2，…，n+1}，1≤i≤n，1≤j≤n

f(uiui+1)=n+2，i∈{1，2，…，n-1}，且i是奇数；f(uiui+1)=n+3，i∈{1，2，…，n-1}，且i是偶数；当n为偶数时，f(unu1)=n+3；当n为奇数时，f(unu1)=n+4

f(vjvj+1)=n+4，j∈{1，2，…，n-1}，且j是奇数；f(vjvj+1)=n+3，j∈{1，2，…，n-1}，且j是偶数

f(ui)=i，1≤i≤n；f(vj)=n+3，j∈{1，2，…，n}，且j是奇数；f(vj)=n+4，j∈{1，2，…，n}，且j是偶数

最终得到的上述全染色是Ⅰ-全染色，并且在此染色下有

C(ui)={i，i+1，(i+2)n+1，…，(i+n-1)n+1，n+2，n+3}，i≠1，n；当n为偶数时，C(u1)={1，2，3，…，n，n+2，n+3}，C(un)={n，n+1，1，…，n-2，n+2，n+3}；当n为奇数时，C(u1)={1，2，…，n，n+2，n+4}，C(un)={n，n+1，1，…，n-2，n+3，n+4}

C(vj)={j，j+1，(j+2)n+1，…，(j+n-1)n+1，n+4，n+3}，j≠n；当n为奇数时，C(vn)={n，n+1，1，…，n-2，n+3}；当n为偶数时，C(vn)={n，n+1，1，…，n-2，n+4}

可见2n个点的色集合彼此互异，故上述Ⅰ-全染色是点可区别的．

定理4 若图G是圈Cm与路Pn(m≥3，n≥2)的联，则

χⅥvt(Cm∨Pn)=χⅠvt(Cm∨Pn).

由命题1知上述定理显然成立．

3 结 语

,χⅥvt(Cn∨Pn)=χⅠvt(Cn∨Pn)=ζ(Cn∨Pn)+1,

χⅥvt(Cm∨Pn)=χⅠvt(Cm∨Pn)=ζ(Cm∨Pn).

点可区别Ⅰ(Ⅵ)-全色数的确定和点可区别正常全色数的确定一样，是困难的问题．目前缺少有效的方法和有力的工具，已得到的相关结论很少，并且其研究主要集中在具体图上．通过本文的讨论，可以看出VDITC猜想及VDVITC猜想对Cm∨Pn(m≥3，n≥2)是成立的：当n=5，6时而对其他的Cm∨Pn有以后将继续对圈和圈、圈和扇及圈和轮的联图的点可区别Ⅰ(Ⅵ)-全色数进行研究．

[1]BURRIS A C, SCHELP R H. Vertex-distinguish proper edge-colorings [J]. Journal of Graph Theory, 1997, 26(2):73-82.

[2]BAZGAN C, HARKAT-BENHAMDINE A, LI Hao,etal. On the vertex-distinguish proper edge-colorings of graphs [J]. Journal of Combinatorial Theory, Series B, 1999, 75(2):288-301.

[3]HARARY F, PLANTHOLT M. The point-distinguishing chromatic index [M] //HARARY F, MAYBEE J S, Eds. Graphs and Application. New York:Wiley Interscience, 1985:147-162.

[5]CHEN Xiang′en. Point-distinguishing chromatic index of the union of paths [J]. Czechoslovak Mathematical Journal, 2014, 64(3):629-640.

[6]ZHANG Zhongfu, QIU Pengxiang, XU Baogen,etal. Vertex-distinguishing total colorings of graphs [J]. Ars Combinatoria, 2008, 87:33-45.

[7]CHEN Xiang′en, MA Yanrong. Vertex-distinguishing total colorings of 2Cn[J]. Chinese Quarterly Journal of Mathematics, 2013, 28(3):323-330.

[8]CHEN Xiang′en, LI Zepeng. Vertex-distinguishing Ⅰ-total colorings of graphs [J]. Utilitas Mathematica, 2014, 95:319-327.

Vertex-distinguishing Ⅰ-total colorings and vertex-distinguishing Ⅵ-total colorings of join-graph of cycle and path

MIAO Tingting1,WANG Zhiwen2,CHEN Xiang′en*1

(1.College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China；2.School of Mathematics and Computer Sciences, Ningxia University, Yinchuan 750021, China )

Ⅰ-total coloring of a graphGis an assignment of several colors to the vertices and edges of graphGsuch that any two adjacent vertices

ifferent colors and any two adjacent edges receive different colors. Ⅵ-total coloring of a graphGis an assignment of several colors to the vertices and edges of graphGsuch that any two adjacent edges receive different colors. For Ⅰ(Ⅵ)-total coloring of graphGand a vertexxof graphG,C(x) is used to denote the set (not multiset) composed of color ofxand colors of the edges incident withx. Letfbe Ⅰ(Ⅵ)-total coloring of a graphGusingkcolors andC(u)≠C(v) for any two different verticesuandvof graphG, thenfis called ak-vertex-distinguishing Ⅰ(Ⅵ)-total coloring of graphG, ork-VDITC (VDVITC) of graphGfor short. The minimum number of colors required in a VDITC (VDVITC) is the vertex-distinguishing Ⅰ(Ⅵ)-total chromatic number. The problems of vertex-distinguishing Ⅰ(Ⅵ)-total colorings of the join-graphCm∨Pnof cycle and path are discussed by the method of combinatorial analysis and constructing concrete coloring. Meanwhile, vertex-distinguishing Ⅰ(Ⅵ)-total chromatic numbers of graphCm∨Pnare determined. The results illustrate that the VDITC conjecture and VDVITC conjecture are valid for graphCm∨Pn.

Ⅰ-total coloring; vertex-distinguishing Ⅰ-total coloring; vertex-distinguishing Ⅰ-total chromatic number; join of cycle and path

1000-8608(2017)04-0430-06

2016-06-25；

2017-06-02．

国家自然科学基金资助项目(61163037，61163054，11261046，61363060)；宁夏回族自治区百人计划资助项目.

苗婷婷(1991-)，女，硕士生，E-mail:miaotingting6130@163.com；陈祥恩*(1965-)，男，教授，硕士生导师，E-mail:chenxe@nwnu.edu.cn.

O157.5

A

10.7511/dllgxb201704015