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

刘秀丽

(菏泽学院 数学系，山东 菏泽 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]. 中北大学学报(自然科学版)，2009，30(1)：1-4. Sun Xiaoling，Du Jianwei. Adjacent vertex distinguishing total coloring of a class of outerplane graphs[J]. Journal of Nouth University of China (Natural Science Edition)，2009，30(1)：1-4. (in Chinese)

[3]张芳红，王治文，陈祥恩.C5∨Kt的邻点可区别全色数[J]. 数学的实践与认识，2012，42(16)：247-252. Zhang Fanghong，Wang Zhiwen，Chen Xiang’en. Adjacent-vertex-distinguishing total chromatic numbers ofC5∨Kt[J]. Mathematics in Practice and Theory，2012，42(16)：247-252. (in Chinese)

[4]Chen X E，Gao Y P，Yao B. Not necessarily proper total colourings which are adjacent vertex distinguishing[J]. International Journal of Computer Mathematics，2013，90(11)：2298-2307.

[5]杨随义，王治文. 一类3-正则图的关联邻点可区别全染色[J]. 山西大学学报(自然科学版)，2010，33(3)：354-357. Yang Suiyi，Wang Zhiwen. Incidence adjacent vertex-distinguishing total coloring of a kind of 3-regular graph[J]. Journal of Shanxi University(Natural Science Edition)，2010，33(3)：354-357. (in Chinese)[6]卢建立，任凤霞，马美琳. 项链的若干染色问题[J]. 科技导报，2012，30(7)：44-47. Lu Jianli，Ren Fengxia，Ma Meilin. Several coloring problems involving necklace[J]. Science and Technology Review，2012，30(7)：44-47. (in Chinese)

[7]杨晓亚. 图Pn□Cm的邻点可区别的I-全染色[J]. 纯粹数学与应用数学，2012，28(6)：757-764. Yang Xiaoya. Adjacent vertex-distinguishingI-total colorings ofPn□Cm[J]. Pure and Applied Mathematics，2012，28(6)：757-764. (in Chinese)

[8]田京京. 冠图Cm·Sn和Cm·Pn的邻点可区别的I-全染色[J]. 西南师范大学学报(自然科学版)，2013，38(2)：25-28. Tian Jingjing. On adjacent Vertex-DistinguishingI-total chromatic number of the crown graphCm·SnandCm·Pn[J]. Journal of Southwest China Normal University(Natural Science Edition)，2013，38(2)：25-28. (in Chinese)

[9]Bondy J A，Murty U S A. Graph theory with apolications[M]. London：Macmillan Press Ltd，1976.

Adjacent Vertex-DistinguishingI-Total Coloring of Some Crown Graphs of Path

LIU Xiu-li

(Dept. of Mathematics，Heze University，Heze 274015，China)

total coloring； adjacent vertex-distinguishing total coloring； adjacent vertex-distinguishingI-total coloring； adjacent vertex-distinguishingI-total chromatic number； crown graph

2016-02-28 基金项目：山东省自然科学基金资助项目(ZR2014AM032)； 山东省高校科技计划资助项目(J13LI02)

刘秀丽(1977-)，女，讲师，硕士，主要从事图论与组合优化的研究.

1673-3193(2016)05-0461-04

O157.5

A

10.3969/j.issn.1673-3193.2016.05.005