Mycielski圖的一般鄰點(diǎn)可區(qū)別全色數(shù)

王繼順

(連云港師范高等專科學(xué)校 數(shù)學(xué)與信息工程學(xué)院，江蘇 連云港 222006)

Mycielski圖的一般鄰點(diǎn)可區(qū)別全色數(shù)

王繼順

(連云港師范高等?？茖W(xué)校 數(shù)學(xué)與信息工程學(xué)院，江蘇 連云港 222006)

Mycielski圖； 一般鄰點(diǎn)可區(qū)別全染色； 一般鄰點(diǎn)可區(qū)別全色數(shù)

由信息科學(xué)中的電信通訊站的頻率分配問題、計(jì)算機(jī)科學(xué)中的網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)區(qū)分問題所引出的點(diǎn)可區(qū)別邊染色[1-3]，鄰點(diǎn)可區(qū)別邊染色[4-5]，鄰點(diǎn)可區(qū)別全染色[6]等具有一定的理論價(jià)值和實(shí)際意義，逐漸成為圖論工作者研究的重要課題[7-10]. 為拓展圖染色理論的應(yīng)用領(lǐng)域，文獻(xiàn)[11]進(jìn)一步提出了一般鄰點(diǎn)可區(qū)別邊染色概念，文獻(xiàn)[12-13]提出圖的一般鄰點(diǎn)可區(qū)別全染色的新染色概念. 由于其同樣是十分困難的問題，至今文獻(xiàn)甚少. 文獻(xiàn)[14]根據(jù)路、圈、扇、輪等圖的結(jié)構(gòu)性質(zhì)，確定了其一般鄰點(diǎn)可區(qū)別的全色數(shù)．

1 相關(guān)定義與猜想

定義1[6]設(shè)G(V，E)是簡單連通圖，k是正整數(shù)，f是V∪E(G)到{1，2，…k}的映射，若f滿足

關(guān)于圖的一般鄰點(diǎn)可區(qū)別全色數(shù)，有2個(gè)猜想.

猜想2[12-13]設(shè)G(V，E)是有n個(gè)頂點(diǎn)的簡單圖，且Δ(G)≥4，則χgat≤Δ(G)+1.

Mycielski圖是圖論中一種重要的圖，也是實(shí)際應(yīng)用中經(jīng)常遇到的一種網(wǎng)絡(luò).文獻(xiàn)[7,15-17]研究了Mycielski圖的相關(guān)染色，筆者從Mycielski圖的構(gòu)造特點(diǎn)出發(fā)，運(yùn)用構(gòu)造法、概率法及色調(diào)整技術(shù)研究了路、圈、扇、星、輪、完全圖和完全二部圖的一般鄰點(diǎn)可區(qū)別全染色問題，得到其一般鄰點(diǎn)可區(qū)別全色數(shù).

文中所涉及的圖都是簡單連通有限圖，未給出的術(shù)語與記號(hào)參見文獻(xiàn)[18].

2 主要結(jié)論與證明

引理1 設(shè)G(V，E)圖為簡單圖，

1) 如果E(G)≠?，則χgat(G)≥2；

2) 如果G(V,E)含K3，則χgat(G)≥3.

引理2 如果G(V，E)含C5，則χgat(G)≥3.

證明不然，根據(jù)引理1 1),χgat(G)≥2. 假設(shè)χgat(G)=2, 不是一般性，對(duì)于G(V，E)首先染其C5.事實(shí)上，令C5=v1v2v3v4v5v1且C(v1)={1}，則f(v2)=1,f(v2v3)=2，或f(v2)=2,f(v2v3)=1,或f(v2)=2,f(v2v3)=2，而f(v3)=2,f(v3v4)=2，或f(v3)=1,f(v3v4)=1根據(jù)如此染色，有

則有C(v5)={1}，{2}或C(v5)={1,2}，但v5與v1，v4是相鄰的頂點(diǎn)，所以與一般鄰點(diǎn)可區(qū)別全染色定義矛盾，故χgat(G)≥3.

定理1設(shè)Pn為n(n≥2)階路，則

χgat(M(Pn))=3.

證明設(shè)Pn=v1v2…vn，分2種情況進(jìn)行證明.

情形1 當(dāng)n=2,注意到M(Pn)=C5，由引理2，χgat(M(Pn))=3[12-13].

則有

定理2設(shè)Cn是n(n≥3)階圈，則

χgat(M(Cn))=3.

證明設(shè)Cn=v1v2…vnv1，分3種情況進(jìn)行討論.

情形1 當(dāng)n=3時(shí)，M(C3)包含有K3, 按照引理1 2), 有χgat(M(C3))≥3.為證結(jié)論成立, 只需給出M(C3)的一個(gè)3-GAVDTC. 令f

易于驗(yàn)證f是M(C3)的一個(gè)3-GAVDTC. 所以χgat(M(Pn))=3.

情形2 當(dāng)n≥4時(shí), 根據(jù)引理2, 有χgat(M(Pn))≥3. 現(xiàn)在只需構(gòu)造M(C3)的一個(gè)3-GAVDTC法f. 為此，從2個(gè)方面考慮.

情形(1) 當(dāng)n≡0(mod 2)時(shí), 令f

f(vivi+1)=1 i=1,2,…,n-1，f(vnv1)=1，

則

易見，f為M(Cn)的一個(gè)3-GAVDTC(n≡0(mod 2)). 所以結(jié)論成立.

情形(2) 當(dāng)n≡1(mod 2)時(shí),令f

f(vi)=1 i≡1(mod 2),f(vi)=3,i≡0(mod 2) i=1, 2,…,n-1,f(vn)=3，

f(vivi+1)=1 i=1,2,…,n-1，f(vnv1)=1，

則

顯然,f是M(Cn)的一個(gè)3-GAVDTC(n≡1(mod 2)).所以結(jié)論成立.

定理3設(shè)Fn是有n+1(n≥2) 個(gè)頂點(diǎn)的扇, 則

χgat(M(Fn))=3.

f(vi)=1 i=0, 1, 2,…,n,f(vivi+1)=1 i=1, 2,…,n-1，

則

顯然, f為M(Fn)的3-GAVDTC. 從而結(jié)論成立.

定理4設(shè)Wn是有n+1(n≥3)個(gè)頂點(diǎn)的輪,則

情形1 當(dāng)n≡0(mod 2)時(shí), 根據(jù)引理1 2),χgat(M(Wn))≥3. 為證結(jié)論成立, 只需構(gòu)造M(Wn)的一個(gè)3-GAVDTC. 令f

f(vivi+1)=1 i=1,2,…,n-1，f(vnv1)=1，

則

顯然，f是M(Wn)的3-GAVDTC. 從而結(jié)論成立.

情形 2 當(dāng)n≡1(mod 2)時(shí), χgat(M(Wn))≥4. 否則, 根據(jù)引理1 2),χgat(M(Wn))≥3. 令χgat(M(Wn))=3, 則所有頂點(diǎn)的色集必是{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}其中之一. 對(duì)于M(Wn)的輪Wn，不失一般性，首先固定頂點(diǎn)v0的色集為C(v0)={1}，由于每個(gè)vi都與v0相鄰，所以頂點(diǎn)vi(i=1, 2,…,n)的色集必是{1, 2}, {1, 3}和{1, 2, 3}其中之一. 由所有的頂點(diǎn)組成圈Cn，且n是奇數(shù)，所以所有的頂點(diǎn)vi(i=1, 2,…,n)的色集含有{1, 2}, {1, 3}和{1, 2, 3},且這些色集是不能有重復(fù)色集相鄰的按序排列下來.不妨令C(v1)={1,3},C(v2)={1, 2},C(vn)={1, 2, 3},則頂點(diǎn)vn-1的色集必然是C(vn-1)={1,2}或C(vn-1)={1,3}.

則

顯然,f是M(Wn)的4-GAVDTC(n≡1(mod 2)).從而結(jié)論成立.

定理5設(shè)完全二部圖為Km,n, 則

χgat(M(Km,n))=3.

證明令(X,Y)為Km,n的二部頂點(diǎn)集對(duì). 根據(jù)引理2, χgat(M(Km,n))≥3.

首先, 用色1, 2和3染M(Km,n)的頂點(diǎn)集X和X′的所有頂點(diǎn)，用色1染所有的邊，然后用色2染頂點(diǎn)集Y和Y′的所有頂點(diǎn)，最后用色3染頂點(diǎn)ω. 顯然該f是M(Km,n)的3-GAVDTC. 結(jié)論成立.

推論1 設(shè)Sn=K1,n是有n+1(n≥2)個(gè)頂點(diǎn)的星, 則

χgat(M(Sn))=3.

證明根據(jù)定理5，結(jié)論顯然.

由上述結(jié)論，關(guān)于Mycielski圖的一般鄰點(diǎn)可區(qū)別全色數(shù)，可得定理6.

定理6設(shè)G(V,E)為任意簡單圖, 則

χgat(G)≤χgat(M(G))≤χgat(G)+1.

[1] Bazgan C, Harkat-Benhamdine H, Li H, et al. On the Vertex-distinguishing proper edge-colorings of Graphs[J].J. Combin Theory: Ser B, 1999, 75(2): 288-301.

[2] Burris A C, Schelp R H. Vertex-distinguishing proper edge-colorings[J]. J. Graph Theory, 1997, 26(2):73-82.

[3] Balister P N, Piordan O M, Schelp R H.Vertex-distinguishing edge colorings of graphs[J].J. Graph Theory, 2003,42:95-105.

[4] Balister P N, Gy?ri E, Lebel J, et al. Adjacent vertex distinguishing edge-colorings[J]. SIAM Journal on Discrete Mathematics, 2006, 21(1):237-250.

[5] Zhang Z F,Liu L Z, Wang J F. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15: 623-626.

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

[7] Chen X E, Zhang Z F, Yan J Z， et al. Adjacent-vertex-distinguishing total chromatic numbers on Mycielski graphs of several kinds of particular graphs[J]. Journal of Lanzhou University (Natural Sciences), 2005,41(2):117-122.

[8] 王繼順，邱澤陽，張忠輔，等．聯(lián)圖Fn∨Pm的鄰點(diǎn)可區(qū)別全染色[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào)，2006, 29(5): 879-884．

[9] Wang H Y. On the adjacent-vertex-distinguishing total chromatic number of the graph with Δ=3[J].Journalof Combinatorial Optimization, 2007, 14(1):87-109.

[10] Chen X E. On the adjacent vertex distinguishing total coloring numbers of graphs with Δ=3[J].DiscreteMathematics, 2008(308):4 003-4 007.

[11] Gy?ri E, Hornak M, Palmer C. General neignbour-distinguishing number of a graph[J].Discrete Mathematics, 2008, 308(5):827-831.

[12] Zhang Z F, Yao B, Li J W, et al. General adjacent-vertex-distinguishing total coloring of graphs[EB/OL]. (2014-06-26).[2016-06-10].http://202.201.18.40:8080/mas5/.

[13] 嚴(yán)謙泰.關(guān)于圖的一般鄰點(diǎn)可區(qū)別全染色[J].系統(tǒng)科學(xué)與數(shù)學(xué), 2010, 30(1):101-106.

[14] 田京京，賈偉，陳祥恩.若干圖類的一般鄰點(diǎn)可區(qū)別全染色算法及其MATLAB實(shí)現(xiàn)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2013, 43(15):227-233.

[15] Liu H M. Circular Chromatic Number and Myceilski Graphs[J]. Acta Mathematica Scientia,2006,26B(2):314-320.

[16] 王繼順. 圖M(Pm)和M(Cm)的點(diǎn)可區(qū)別邊色數(shù)[J].數(shù)學(xué)雜志，2012，32(2): 363-368.

[17] 馬剛. 若干Mycielski圖的點(diǎn)可區(qū)別均勻全色數(shù)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012, 42(9): 207-213.

[18] Bondy J A,Murty U S R. Graph Theory[M]. New York: Springer, 2008.

General Adjacent Vertex-distinguishing Total Coloring Chromatic Number of Mycielski Graphs

Wang Jishun

(School of Mathematics and Information Engineering, Lianyungang Teacher’s College, Lianyungang 222006, China)

Mycielski Graph; General adjacent vertex distinguishing total coloring; General adjacent vertex distinguishing total chromatic number

2016-06-22

國家自然科學(xué)基金(61170302)；連云港市第五期“521”人才培養(yǎng)工程資助項(xiàng)目

王繼順(1970-)，男，山東臨沭人，副教授，研究方向：圖論染色及其應(yīng)用，E-mail:wjishun@163.com

1004-1729(2016)04-0307-06

O 157.5

A DOl：10.15886/j.cnki.hdxbzkb.2016.0046