劉秀麗

(菏澤學(xué)院 數(shù)學(xué)系，山東 菏澤 274015)

?

若干路的冠圖的鄰點(diǎn)可區(qū)別I-全染色

劉秀麗

(菏澤學(xué)院 數(shù)學(xué)系，山東 菏澤 274015)

全染色； 鄰點(diǎn)可區(qū)別全染色； 鄰點(diǎn)可區(qū)別I-全染色； 鄰點(diǎn)可區(qū)別I-全色數(shù)； 冠圖

0 引 言

圖的染色問(wèn)題是圖論的主要研究?jī)?nèi)容之一，全染色問(wèn)題特別是鄰點(diǎn)可區(qū)別全染色又是染色問(wèn)題中的難點(diǎn). 2004年，張忠輔等[1]提出了鄰點(diǎn)可區(qū)別全染色的概念，這個(gè)染色問(wèn)題已經(jīng)被廣泛研究[2-3]. 在鄰點(diǎn)可區(qū)別全染色概念的基礎(chǔ)上，又提出了圖的鄰點(diǎn)可區(qū)別I-全染色[4]的概念. 近來(lái)，一些學(xué)者對(duì)一些特殊圖類的鄰點(diǎn)可區(qū)別I-全染色進(jìn)行了研究[5-8]. 本文討論了Pn°Pm，Pn°Cm，Pn°Fm和Pn°Wm圖的鄰點(diǎn)可區(qū)別I-全染色，根據(jù)這些圖的構(gòu)造特征，給出了一種具體的染色方案，得到了它們的鄰點(diǎn)可區(qū)別I-全色數(shù)，并且滿足猜想.

定義 1[4]對(duì)于階數(shù)不小于2的連通圖G，f是從V(G)∪E(G)到{1,2,…,k}的映射，k是自然數(shù)，如果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]對(duì)于路Pn和任意給定的圖H，先將H進(jìn)行n次復(fù)制，然后將路Pn中的每個(gè)頂點(diǎn)懸掛H，且每個(gè)公共點(diǎn)都是H中的點(diǎn)v0，這樣構(gòu)造得到的圖稱為路的冠圖，記為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}.

本文所討論的圖均為簡(jiǎn)單、有限圖. 文中未加說(shuō)明的記號(hào)和術(shù)語(yǔ)參見(jiàn)文獻(xiàn)[9].

1 主要結(jié)果及證明

定理 1對(duì)圖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.

此時(shí)，

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.

此時(shí)，

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對(duì)圖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.

此時(shí)，

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.

此時(shí)，

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對(duì)圖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.

此時(shí)，

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.

此時(shí)，

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對(duì)圖Pn°Fm，n≥3，m≥3， 則有

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

[1]張忠輔，陳祥恩，李敬文，等. 關(guān)于圖的鄰點(diǎn)可區(qū)別全染色[J]. 中國(guó)科學(xué)(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]孫曉玲，杜建偉. 一類外平面圖的鄰點(diǎn)可區(qū)別全染色[J]. 中北大學(xué)學(xué)報(bào)(自然科學(xué)版)，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的鄰點(diǎn)可區(qū)別全色數(shù)[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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-正則圖的關(guān)聯(lián)鄰點(diǎn)可區(qū)別全染色[J]. 山西大學(xué)學(xué)報(bào)(自然科學(xué)版)，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]盧建立，任鳳霞，馬美琳. 項(xiàng)鏈的若干染色問(wèn)題[J]. 科技導(dǎo)報(bào)，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的鄰點(diǎn)可區(qū)別的I-全染色[J]. 純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，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的鄰點(diǎn)可區(qū)別的I-全染色[J]. 西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，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 基金項(xiàng)目：山東省自然科學(xué)基金資助項(xiàng)目(ZR2014AM032)； 山東省高?？萍加?jì)劃資助項(xiàng)目(J13LI02)

劉秀麗(1977-)，女，講師，碩士，主要從事圖論與組合優(yōu)化的研究.

1673-3193(2016)05-0461-04

O157.5

A

10.3969/j.issn.1673-3193.2016.05.005