兩類k重Mycielski圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色

李雨虹, 強(qiáng)會(huì)英, 王洪申

(1.蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院, 甘肅 蘭州 730070;2.蘭州理工大學(xué) 機(jī)電工程學(xué)院，甘肅 蘭州 730050)

兩類k重Mycielski圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色

李雨虹1, 強(qiáng)會(huì)英1, 王洪申2

(1.蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院, 甘肅 蘭州 730070;2.蘭州理工大學(xué) 機(jī)電工程學(xué)院，甘肅 蘭州 730050)

應(yīng)用反證法和構(gòu)造染色函數(shù)法研究了圖Mk(Fn)和Mk(Wn)的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色,并得出了其鄰點(diǎn)強(qiáng)可區(qū)別E-全色數(shù).

鄰點(diǎn)強(qiáng)可區(qū)別全染色;k重Mycielski圖; 鄰點(diǎn)強(qiáng)可區(qū)別E-全染色

0 引言

圖論在網(wǎng)絡(luò)設(shè)計(jì)、信息科學(xué)、密碼學(xué)、DNA的基因普的確定和計(jì)數(shù)等領(lǐng)域有著廣泛的應(yīng)用. 其中圖的染色問題是圖論中的經(jīng)典問題之一，它源自四色定理猜想以及哈密頓等問題的出現(xiàn)，其在組合分析和實(shí)際生活中也有著廣泛的應(yīng)用.1993年，Burris A C和Schelp R H首先提出了點(diǎn)可區(qū)別邊染色的概念及猜想[1]；2002年，張忠輔，劉林忠等人提出了鄰強(qiáng)邊染色的概念以及猜想[2]；2005年，張忠輔和陳祥恩又提出了具有廣泛應(yīng)用背景的圖的鄰點(diǎn)可區(qū)別全染色的概念以及猜想[3]；2008年，張忠輔，程輝等人從實(shí)際問題出發(fā)，進(jìn)一步提出圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色的概念及猜想[4]；2010年，程輝和王志勇等人根據(jù)圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色提出了鄰點(diǎn)強(qiáng)可區(qū)別EI-全染色的概念[5]. 本文在此基礎(chǔ)上，得到了兩類特殊圖Mk(Fn)和Mk(Wn)的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色，并得出了其相應(yīng)的染色數(shù).

1 預(yù)備知識(shí)

定義1[6]設(shè)圖G是階數(shù)至少為2的連通圖,映射f:V(G)∪E(G)→{1,2,…,k}, 其中k為正整數(shù),C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G),v∈V(G)}. 如果f滿足:

1) 對(duì)任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);

2) 對(duì)任意的uv,uw∈E(G),u≠w,f(uv)≠f(uw);

3) 對(duì)任意的uv∈E(G),u≠v,C(u)≠C(v)．

則稱f為圖G的k-鄰點(diǎn)強(qiáng)可區(qū)別全染色,簡(jiǎn)記為k-AVSDTC,又稱χast(G)=min{k|G有k-AVSDTC}為G的鄰點(diǎn)強(qiáng)可區(qū)別全色數(shù).

定義2[6]設(shè)圖G是階數(shù)至少為2的連通圖, 映射f:V(G)∪E(G)→{1,2,…,k}, 其中k為自然數(shù),C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G),v∈V(G)}. 如果f滿足:

1) 對(duì)任意的uv∈E(G),u≠v,f(u)≠f(v),f(u)≠f(uv);

2) 對(duì)任意的uv∈E(G),u≠v,C(u)≠C(v).

由圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色和圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色的概念,下面引理成立:

定義3[7]設(shè)G的頂點(diǎn)集合為V(G)={u1i|i=1,2,…,n}的簡(jiǎn)單圖,n是正整數(shù),稱Mk(G)為G的k重Mycielski圖,其中k≥2, 如果

V(Mk(G))={u1,1,u1,2,…,u1,n;u2,1,u2,2,…,u2,n;…;uk,1,…,uk,n;}∪{w}

E(Mk(G))=E(M(G))∪{uijui+1,l|u1ju1l∈E(G),1≤j,l≤n,1≤i≤k-1,}∪

{wvkj|vkj∈V(G),1≤j≤n}.

2 主要結(jié)論

由圖的結(jié)構(gòu)知,|C(w)|≥4,下面分兩種情形考慮:

情形1 當(dāng)|C(w)|=4時(shí), 則點(diǎn)uij(除了u1j)和點(diǎn)w在鄰點(diǎn)強(qiáng)可區(qū)別E-全染色的條件下,必存在j∈{1,2,…,n}, 使得C(u1j)=C(u1,j+1), 與定義矛盾.

情形2 當(dāng)|C(w)|=5時(shí),必存在j∈{1,2,…,n}, 使得C(ukj)=C(w), 與定義矛盾.

f(ui1)=1,1≤i≤k.f(w)=6.f(u1ju1,j+1)=1, 2≤j≤n-1.

邊uijui+1,l的染法如下:

f(u1ju2,j-1)=5, 3≤j≤n.f(u1ju2,j+1)=5, 2≤j≤n-1.

當(dāng)k≡1(mod4)或k≡2(mod4)時(shí)f(wvkj)=4, 1≤j≤n.

此時(shí),各點(diǎn)色集合的補(bǔ)集為:

顯然, 對(duì)?uv∈E(G),有C(u)≠C(v), 故結(jié)論成立.

定理2 設(shè)Wn是n(n≥4)階的輪圖,則有

證明下面分兩種情況討論:

由圖的結(jié)構(gòu)知,|C(w)|≥5,下面分兩種情形考慮:

情形1.1 當(dāng)|C(w)|=5時(shí), 則點(diǎn)uij(除了u1j)和點(diǎn)w在鄰點(diǎn)強(qiáng)可區(qū)別E-全染色的條件下,必存在j∈{1,2,…,n}, 使得C(u1j)=C(u1,j+1), 與定義矛盾.

情形1.2 當(dāng)|C(w)|=6時(shí),必存在j∈{1,2,…,n}, 使得C(ukj)=C(w), 與定義矛盾.

邊uijui+1,l的染法如下:

f(u1ju21)=2,j=n-1;n.f(u1ju2,j-1)=1, 3≤j≤n.

f(u1ju2,j+1)=1,2≤j≤n-1.

此時(shí),各點(diǎn)的色集合的補(bǔ)集為:

顯然, 對(duì)?uv∈E(G),,有C(u)≠C(v), 故結(jié)論成立.

f(ui1)=1,1≤i≤k.f(w)=6.f(u1ju1,j+1)=1,2≤j≤n-1.

邊uijui+1,l的染法如下:

f(u1ju2,j-1)=5, 3≤j≤n.f(u1ju2,j+1)=5,2≤j≤n-1.

當(dāng)k≡1(mod4)或k≡2(mod4)時(shí)f(wvkj)=4, 1≤j≤n.

此時(shí),各點(diǎn)色集合的補(bǔ)集為:

顯然, 對(duì)?uv∈E(G),,有C(u)≠C(v), 故結(jié)論成立.

[1] Burris A C. Vertex-distinguishing edge-colorings[D].Memphis State University,1993.

[2] Zhong Z F,Liu Z L,Jiang F W. Adjacent Strong Edge-Coloring of Graph[J]. Applied Mathematic letter,2002,15(5):623-626.

[3] Zhang Z F,Chen X G,Li J W,et al. On adjacent vertex-distinguishing total coloring of graphs[J]. Science in China: Ser A Mathmatics,2005,48(3): 289-299.

[4] Zhang Z F,Chen X G. On adjacent-vertex-strongly-distinguishing total coloring of graphs[J]. Science in China.Series A: Mathmatics,2008,51(3): 427-436.

[5] Chen X G,Wang Z Y. Adjacent vertex-strongly-distinguishingE-total coloring of graphs[J]. Shan dong Univ Nat Sci,2010(6):18-22.

[6] 顧忠棟,強(qiáng)會(huì)英,魏邦魁.兩類特殊圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色[J].蘇州科技學(xué)院學(xué)報(bào)(自然科學(xué)版).2016,35(3):18-21.

[7] 強(qiáng)會(huì)英,晁福剛,張忠輔. 完全圖的廣義Mycielski圖的鄰點(diǎn)可區(qū)別全色數(shù)[J].蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,41(6):102-105.

OnAdjacentVertexStronglyDistinguishingE-totalColoringofTwoclassesk-multi-MycielskiGraphs

LI Yu-hong1, QIANG Hui-ying1, WANG Hong-shen2

(1.School of Mathematics, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China)(2.School of Mechatronic Engineering, Lanzhou University of Technology, Lanzhou Gansu 730050, China)

The adjacent vertex strongly distinguishingE-total coloring ofk-multi-Mycielski Graphs ofMk(Fn)andMk(Wn) are givening by contradiction and constructing colorable function, meanwhile, the adjacent vertex strongly distinguishingE-total chromatic of them are obtained.

adjacent vertex strongly distinguishing total coloring;k-multi-Mycielski graphs; adjacent vertex strongly distinguishingE-total coloring

O157.5

A

1671-6876(2017)03-0205-05

[責(zé)任編輯李春紅]

2017-06-06

國家自然科學(xué)基金資助項(xiàng)目(11461038; 11561042)

強(qiáng)會(huì)英(1968-),女,甘肅白銀人,教授,研究方向?yàn)閳D論與組合優(yōu)化. E-mail: qhy2005ww@126.com