李雨虹, 強會英, 王洪申

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

兩類k重Mycielski圖的鄰點強可區(qū)別E-全染色

李雨虹1, 強會英1, 王洪申2

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

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

鄰點強可區(qū)別全染色;k重Mycielski圖; 鄰點強可區(qū)別E-全染色

0 引言

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

1 預備知識

定義1[6]設圖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) 對任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);

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

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

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

定義2[6]設圖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) 對任意的uv∈E(G),u≠v,f(u)≠f(v),f(u)≠f(uv);

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

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

定義3[7]設G的頂點集合為V(G)={u1i|i=1,2,…,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 當|C(w)|=4時, 則點uij(除了u1j)和點w在鄰點強可區(qū)別E-全染色的條件下,必存在j∈{1,2,…,n}, 使得C(u1j)=C(u1,j+1), 與定義矛盾.

情形2 當|C(w)|=5時,必存在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.

當k≡1(mod4)或k≡2(mod4)時f(wvkj)=4, 1≤j≤n.

此時,各點色集合的補集為:

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

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

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

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

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

情形1.2 當|C(w)|=6時,必存在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.

此時,各點的色集合的補集為:

顯然, 對?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.

當k≡1(mod4)或k≡2(mod4)時f(wvkj)=4, 1≤j≤n.

此時,各點色集合的補集為:

顯然, 對?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] 顧忠棟,強會英,魏邦魁.兩類特殊圖的鄰點強可區(qū)別E-全染色[J].蘇州科技學院學報(自然科學版).2016,35(3):18-21.

[7] 強會英,晁福剛,張忠輔. 完全圖的廣義Mycielski圖的鄰點可區(qū)別全色數(shù)[J].蘭州大學學報(自然科學版),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

[責任編輯李春紅]

2017-06-06

國家自然科學基金資助項目(11461038; 11561042)

強會英(1968-),女,甘肅白銀人,教授,研究方向為圖論與組合優(yōu)化. E-mail: qhy2005ww@126.com