刘秀丽

(菏泽学院 数学系，山东 菏泽 274015)



若干路的冠图的邻点可区别I-全染色

刘秀丽

(菏泽学院 数学系，山东 菏泽 274015)

全染色； 邻点可区别全染色； 邻点可区别I-全染色； 邻点可区别I-全色数； 冠图

0 引 言

图的染色问题是图论的主要研究内容之一，全染色问题特别是邻点可区别全染色又是染色问题中的难点. 2004年，张忠辅等[1]提出了邻点可区别全染色的概念，这个染色问题已经被广泛研究[2-3]. 在邻点可区别全染色概念的基础上，又提出了图的邻点可区别I-全染色[4]的概念. 近来，一些学者对一些特殊图类的邻点可区别I-全染色进行了研究[5-8]. 本文讨论了Pn∘Pm，Pn∘Cm，Pn∘Fm和Pn∘Wm图的邻点可区别I-全染色，根据这些图的构造特征，给出了一种具体的染色方案，得到了它们的邻点可区别I-全色数，并且满足猜想.

定义 1[4]对于阶数不小于2的连通图G，f是从V(G)∪E(G)到{1,2,…,k}的映射，k是自然数，如果f满足:

1) 任意uv∈E(G)，u≠v，有f(u)≠f(v)；

2) 任意uv，uw∈E(G)，v≠w，有f(uv)≠f(uw)；

3) 任意uv∈E(G)，u≠v，有C(u)≠C(v).

定义 2[8]对于路Pn和任意给定的图H，先将H进行n次复制，然后将路Pn中的每个顶点悬挂H，且每个公共点都是H中的点v0，这样构造得到的图称为路的冠图，记为Pn∘H.

V(Pn∘Pm)={vi,j|i=1,2,…,n,j=0,1,2,…,m-1}，

E(Pn∘Pm)={vi,0vi+1,0|i=1,2,…,n-1}∪ {vi,jvi,j+1|i=1,2,…,n，j=0,1,2,…,m-2}.

V(Pn∘Cm)={vi,j|i=1,2,…,n，j=0,1,2,…,m-1}，

E(Pn∘Cm)={vi,0vi+1,0|i=1,2,…,n-1}∪{vi,jvi,j+1|i=1,2,…,n，j=0,1,2,…,m-2}∪ {vi，m-1vi,0|i= 1,2,…,n}.

V(Pn∘Fm)={vi,j|i=1,2,…,n，j=0,1,2,…,m}，

E(Pn∘Fm)={vi,0vi+1,0|i=1,2,…,n-1}∪{vi,jvi,j+1|i=1,2,…,n，j=1,2,…,m-1}∪{vi,0vi,j|i=1,2,…,n，j=1,2,…,m}.

V(Pn∘Wm)={vi,j|i=1,2,…,n，j=0， 1,2,…,m} ，

E(Pn∘Wm)={vi,0vi+1,0|i=1,2,…,n-1}∪{vi,jvi,j+1|i=1,2,…,n，j=1,2,…,m-1}∪{vi，mvi，1|i=1,2,…,n}∪{vi,0vi,j|i=1,2,…,n，j=1,2,…,m}.

本文所讨论的图均为简单、有限图. 文中未加说明的记号和术语参见文献[9].

1 主要结果及证明

定理 1对图Pn∘Pm，n≥3，m≥2，则有

证明1)n=3.

f(v1,0)=1，f(v2,0)=2，f(v3,0)=3，

f(v1,0v2,0)=1，f(v2,0v3,0)=2，

j=1,2,…,m-1,

i=2,3, j=0,1,2,…, m-2.

此时，

C(v1,0)={1，2}，

C(v2,0)={1，2，3}，

C(v3,0)={2，3}，

i=2,3, j=1,2,…,m-2,

2)n≥4.

i=1,2,…,n, f(v1,0v2,0)=2，

i=2,3,…,n-1,

i=1,2,…,n, j=1,2,…,m-1,

i=1,2,…,n, j=0,1,2,…,m-2.

此时，

i=3,4,…,n-1,

C(v1,0)={1,2}，C(v2,0)={1,2,4}，

i=1,2,3,…,n, j=1,2,…,m-2,

i=1,2,3,…,n.

定理 2对图Pn∘Cm，n≥3，m≥3，则有

证明1)n=3.

f(v1,0)=4，f(v2,0)=2，f(v3,0)=4，

f(v1,0v2,0)=1，f(v2,0v3,0)=3，

i=1,2,3, j=1,2,…,m-1,

j=0,1,2,…,m-2,

f(vi,m-1vi,0)=4，i=1,2,3.

此时，

C(v1,0)={1,2,4}，C(v2,0)={1,2,3,4}，

C(v3,0)={2,3,4}，

i=1,2,3, j=1,2,…,m-2,

i=1,2,3.

2)n≥4.

i=1,2,3,…,n-1,

i=1,2,…,n, j=1,2,…,m-1,

j=0,1,2,…,m-2,

f(vi,m-1vi,0)=4，i=1,2,…,n.

此时，

i=2,3,…,n-1,

C(v1,0)={1,2,4}，

i=1,2,3,…,n, j=1,2,…,m-2,

i=1,2,3,…,n.

定理 3对图Pn∘Wm，n≥3，m≥3，则有

证明1)n=3.

f(v1,0)=m+1，f(v2,0)=m+2，f(v3,0)=m+1，f(v1,0v2,0)=m+1，f(v2,0v3,0)=m+2，

f(vi,j)=j，f(vi,0vi,j)=j，i=1,2，j=1,2,…,m，

f(v3，j)=j，f(v3,0v3,j)=j，j=1,2,…,m-1，f(v3,0v3,m)=m+1，

f(vi,jvi,j+1)=j+3，j=1,2,…,m-1，

f(vi，mvi,1)=2，i=1,2,3.

此时，

C(v1,0)={1,2,…,m,m+1}，C(v2,0)={1,2,…,m,m+1，m+2}，

C(v3,0)={1，2，…，m-1,m+1,m+2}，

C(vi,j)={j,j+2,j+3}，i=1,2,3，j=2,3,…,m-1，

C(vi,1)={1,2,4}，C(vi,m)={2,m,m+2}，i=1,2，C(v3,m)={2,m+1,m+2}.

2)n≥4.

f(vi,j)=j，f(vi,0vi,j)=j，i=1,2,…,n，j=1,2,…,m，

f(vi,jvi,j+1)=j+3，j=1,2,…,m-1，

f(vi，mvi,1)=2，i=1,2,…,n.

此时，

C(v1,0)={1,2,…,m,m+1,m+2}，

i=2,3,…,n-1

C(vi,j)={j,j+2,j+3}，i=1,2,3,…,n，j=2,3,…,m-1，

C(vi,1)={1,2,4}，C(vi,m)={2,m,m+2}，i=1,2,3,…,n.

定理 4对图Pn∘Fm，n≥3，m≥3， 则有

证明由定理3可直接得出.

[1]张忠辅，陈祥恩，李敬文，等. 关于图的邻点可区别全染色[J]. 中国科学(A辑)，2004，34(5)：574-583. Zhang Zhongfu，Chen Xiang’en，Li Jingwen，et al. Adjacent vertex distinguishing total coloring of graph[J]. Science in China(Ser. A)，2004，34(5)：574-583. (in Chinese)

[2]孙晓玲，杜建伟. 一类外平面图的邻点可区别全染色[J]. 中北……