Wm與Pn(n≤3)聯(lián)圖的點(diǎn)可區(qū)別邊色數(shù)＊

王國興

(蘭州商學(xué)院信息工程學(xué)院,甘肅蘭州730020)

Wm與Pn(n≤3)聯(lián)圖的點(diǎn)可區(qū)別邊色數(shù)＊

王國興

(蘭州商學(xué)院信息工程學(xué)院,甘肅蘭州730020)

設(shè)G是簡單圖,圖G的一個k-點(diǎn)可區(qū)別正常邊染色f是指一個從E(G)到{1,2,…,k}的映射,且滿足?u,v∈V(G),u≠v,有S(u)≠S(v),其中S(u)={f(uw)|uw∈E(G)}.數(shù)min{k|G存在k-VDPEC染色}稱為圖G的點(diǎn)可區(qū)別正常邊色數(shù),記為研究了Wm∨Pn(n≤3)的點(diǎn)可區(qū)別邊染色,給出了Wm∨Pn(n≤3)的點(diǎn)可區(qū)別邊色數(shù).

聯(lián)圖;點(diǎn)可區(qū)別邊染色;點(diǎn)可區(qū)別邊色數(shù)

圖的染色問題是圖論研究的主要內(nèi)容之一.圖的染色的基本問題就是確定其各種染色法的色數(shù).Burris, Schelp等人提出點(diǎn)可區(qū)別邊染色的概念,得到了若干結(jié)果,并提出了有關(guān)猜想[1～3].文獻(xiàn)[4～7]研究了一些圖的點(diǎn)可區(qū)別正常邊染色.本文給出了點(diǎn)Wm∨Pn(n≤3)可區(qū)別正常邊染色.

1 預(yù)備知識

定義1[1～3]設(shè)f是圖G的一個使用了k種色1,2,…,k的正常邊染色,對任意的u∈V(G)記S(u)= {f(uw)|uw∈E(G)},稱S(u)為點(diǎn)u在f下的色集合.并且記(u)={1,2,…,k}S(u).如果對?u,v∈ V(G),u≠v,有S(u)≠S(v),那么稱f是圖G的一個k-點(diǎn)可區(qū)別正常邊染色,簡記為k-VDPEC,且稱(G)=min{k圖G存在k-VDPEC}為G的點(diǎn)可區(qū)別正常邊色數(shù).

若S(u)≠S(v),則稱u與v是可區(qū)別的.顯然給出G的一個正常邊染色之后,為證它是點(diǎn)可區(qū)別的,只需說明任意兩個同度點(diǎn)可區(qū)別即可.顯然,圖G存在點(diǎn)可區(qū)別正常邊染色當(dāng)且僅當(dāng)G沒有孤立邊且最多有一個孤立點(diǎn).

對圖G,令nk表示度為k的頂點(diǎn)個數(shù),δ≤k≤Δ,設(shè)

猜想[1～3]若G是沒有孤立邊并且最多有一個孤立點(diǎn)的圖,則(G)或μ(G)+1.

定義[8]設(shè)G和H是點(diǎn)不相交且邊不交的簡單圖,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)},則稱G∨H是G與H的聯(lián)圖.引理1[1]對n≥3的n階完全圖Kn,有

本文中總記m+1階的輪Wm的頂點(diǎn)集為V(Wm)={ui|i=0,1,…,m},邊集為E(Wm)={u0ui|i=1,…, m}∪{uiui+1|i=1,…,m-1}∪{umu1}.記n階的路Pn的頂點(diǎn)集為V(Pn)={vj|j=1,2,…,n},邊集為E (Pn)={vjvj+1|j=1,2,…,n-1}.

2 主要結(jié)論

定理1 當(dāng)m≥3時,

證明 分以下兩種情況考慮.

情形1 當(dāng)m=3時,W3∨P1=K5,由引理1知結(jié)論成立,即

1)當(dāng)m=4時,給出W4∨P1的一個使用了顏色為1,2,3,4,5,6的邊染色如下:

u0u1,u0u2,u0u3,u0u4依次用2,3,4,5去染;v1u1,v1u2,v1u3,v1u4,依次用1,2,3,4去染;v1u0用6去染; u1u2,u2u3,u3u4,u4u1依次用4,6,1,6去染.

對上述染色,有S(u1)={1,2,4,6},S(u2)={2,3,4,6},S(u3)={1,3,4,6},S(u4)={1,4,5,6}, S(u0)={2,3,4,5,6},S(v1)={1,2,3,4,6}.因此,上述染色是W4∨P1的使用了6種色點(diǎn)可區(qū)別正常邊染色.

2)當(dāng)m>4時,給出Wm∨P1的一個使用了顏色為1,2,…,m+2的邊染色如下:

u0u1,u0u2,…,u0um依次用2,3,…,m+1去染;v1u1,v1u2,…,v1um依次用1,2,3,…,m去染;v1u0用m+ 2去染;u1u2,u2u3,…,um-1um,umu1依次用4,5,6,…,m+2,3去染.

對上述染色,有S(u0)={2,3,…,m,m+2},S(ui)={i,i+1,i+2,i+3},i=1,2,…,m-1.

S(um)={3,m,m+1,m+2},S(v1)={1,2,…,m,m+2}.

綜合上述染色兩種情況,定理1為真.

定理2 當(dāng)m≥3時,

證明 分以下兩種情況考慮.

情形1 當(dāng)m=3時,W3∨P2=K6,由引理1知結(jié)論成立,即

1)當(dāng)m=4時,給出W4∨P2的一個使用了染色為1,2,3,4,5,6,7的邊染色如下:

u1u2,u2u3,u3u4,u4u1依次用1,2,3,7去染;v1u1,v1u2,v1u3,v1u4依次用2,3,4,5去染;v2u1,v2u2,v2u3, v2u4依次用3,4,5,6去染;u0u1,u0u2,u0u3,u0u4依次用4,5,6,1去染;u0v1,u0v2,v1v2依次用7,2,1去染.

對上述染色,有S(u1)={1,2,3,4,7},S(u2)={1,2,3,4,5},S(u3)={2,3,4,5,6},S(u4)={1,3,5, 6,7},S(u0)={1,2,4,5,6,7},S(v1)={1,2,3,4,5,7},S(v2)={1,2,3,4,5,6}.

2)當(dāng)m=5時,給出W5∨P2的一個使用了顏色為1,2,3,4,5,6,7,8的邊染色如下:

u1u2,u2u3,u3u4,u4u5,u5u1依次用1,2,3,8,5去染;v1u1,v1u2,v1u3,v1u4,v1u5依次用2,3,4,5,6去染; v2u1,v2u2,v2u3,v2u4,v2u5依次用3,4,5,6,7去染;u0u1,u0u2,u0u3,u0u4,u0u5依次用6,7,8,4,3去染;u0v1, u0v2,v1v2依次用1,2,8去染.

3)當(dāng)m≥6時,給出Wm∨P2的一個使用了顏色1,2,…,m+2,m+3的邊染色如下:

u1u2,u2u3,…,um-1um,umu1依次用1,2,3…,m-1,m去染;u0u1,u0u2,…,u0um依次用4,5,…,m+3去染;v1u1,v1u2,…,v1um依次用2,3,…,m+1去染;v2u1,v2u2,…,v2um依次用3,4…,m+2去染;u0v1,u0v2, v1v2依次用1,2,m+3去染.

因此,上述染色是點(diǎn)可區(qū)別正常邊染色,所以m>3當(dāng)時

綜合上述染色兩種情況,定理2為真.

定理3 當(dāng)m≥3時,

證明 當(dāng)m≥3時,有

μ(Wm∨P3)

分以下五種情況考慮.

情形1 當(dāng)m=3時,μ(W3∨P3)

下面給出W3∨P3的一個使用了顏色為1,2,3,4,5,6,7的邊染色如下:

u1u2,u2u3,u3u1依次用1,2,3去染;u0u1,u0u2,u0u3依次用2,3,4去染;v1u1,v1u2,v1u3依次用4,5,6去染;v2u1,v2u2,v2u3依次用5,6,7去染;v3u1,v3u2,v3u3依次用6,7,1去染;u0v1,u0v2,u0v3依次用7,1,5去染; v1v2,v2v3依次用3,4去染.

S(v2)={2},S (v3)={2,3}.

情形2 當(dāng)m=4時,μ(W4∨P3)

下面給出W4∨P3的一個使用了顏色為1,2,3,4,5,6,7,8的邊染色如下:

u1u2,u2u3,u3u4,u4u1依次用1,2,3,4去染;u0u1,u0u2,u0u3,u0u4依次用7,3,4,5去染;v1u1,v1u2,v1u3, v1u4依次用3,4,5,6去染;v2u1,v2u2,v2u3,v2u4依次用5,6,7,8去染;v3u1,v3u2,v3u3,v3u4依次用6,7,8,2去染;u0v1,u0v2,u0v3,v1v2,v2v3依次用8,2,1,1,3去染.

情形3 當(dāng)m=5時,μ(W5∨P3)

下面給出W5∨P3的一個使用了顏色為1,2,3,4,5,6,7,8,9的邊染色如下:

u1u2,u2u3,u3u4,u4u5,u5u1依次用1,2,3,4,5去染;u0u1,u0u2,u0u3,u0u4,u0u5依次用8,9,4,5,6去染; v1u1,v1u2,v1u3,v1u4,v1u5依次用3,4,5,6,7去染;v2u1,v2u2,v2u3,v2u4,v2u5依次用4,5,6,7,8去染;v3u1, v3u2,v3u3,v3u4,v3u5依次用6,7,8,9,1去染;u0v1,u0v2,u0v3,v1v2,v2v3依次用2,1,3,9,2去染.

情形4 當(dāng)m=6時,μ(W6∨P3)

下面給出W6∨P3的一個使用了顏色為1,2,3,4,5,6,7,8,9,10的邊染色如下:

u1u2,u2u3,u3u4,u4u5,u5u6,u6u1依次用1,2,3,4,5,6去染;u0u1,u0u2,u0u3,u0u4,u0u5,u0u6依次用8,3, 4,5,6,7去染;v1u1,v1u2,v1u3,v1u4,v1u5,v1u6依次用3,4,5,6,7,8去染;v2u1,v2u2,v2u3,v2u4,v2u5,v2u6依次用4,5,6,7,8,9去染;v3u1,v3u2,v3u3,v3u4,v3u5,v3u6依次用6,7,8,9,10去染;u0v1,u0v2,u0v3,v1v2,v2v3依次用1,10,2,2,1去染.

情形5 當(dāng)m≥7時,給出Wm∨P3的一個使用了顏色為1,2,…,m+3,m+4的邊染色如下:

u1u2,u2u3,u3u4,…,um-2um-1,um-1um,umu1依次用1,2,3,…m-2,m-1,m去染;u0u1,u0u2,…,u0um-1, u0um依次用5,6,…,m+3,m+4去染;v1u1,v1u2,…,v1um-1,v1um依次用2,3,…,m,m+1去染;v2u1,v2u2,…,v2um-1,v2um依次用3,4,…,m+1,m+2去染;v3u1,v3u2,…,v3um-1,v3um依次用4,5,…,m+2,m+3去染,u0v1,u0v2,u0v3,v1v2,v2v3依次用1,2,3,m+4,1去染.

綜合上述五種情況,有S(u)≠S(v),對?u,v∈V(Wm∨P3),u≠v,所以上述所給染色是Wm∨P3的使用了m+4種色的點(diǎn)可區(qū)別正常染色.即有

定理3為真.

[1]BurrisA C,Schelp R H.Vertex-distingguishing proper edge-coloring[J].J of Graph Theory,1997,26(2):73-82.

[2]Bazgan C,Harkat-Benhamdine A,Li H,et al.On the Vertex-distinguishing proper edge-coloring[J].Combin Theory SerB, 1999,75(2):288-301.

[3]Balister P N,BollobasB,Shelp R H.Vertex-distinguishing coloring of graph with 2[J].Discrete Mathematics,2002,252(2): 17-29.

[4]Zhang Zhongfu,liu Linzhong,Wang Jianfang.Adiacent strong edge coloring of graph[J].Applied Mathematics Letters,2002,15 (5):623-626.

[5]王國興.Wm∨C3的點(diǎn)可區(qū)別正常邊色數(shù)[J].佳木斯大學(xué)學(xué)報:自然科學(xué)版,2010,28(1):144-145.

[7]陳祥恩,張忠輔.K-tn的點(diǎn)可區(qū)別正常邊染色[J].數(shù)學(xué)研究,2004,37(4):376-380.

[8]Bondy J A,MurtyU S R.Graphs theorywith application[M].New York:TheMacmlllan PressLtd,1976.

Vertex D ist inguishing Edge Chromatic Numbers of the Jo in of the GraphsWmand path Pn(n≥3)

WANG Guo-xing

(School of Information Engineering,Lanzhou University of Finance and Economics,Lanzhou Gansu 730020,China)

LetGbe a simple graph.An nor mal coloringfofGrefers to a coloring of the vertices ofGso that no two adjacent vertices receive the same color.LetS(u)be the set of colors of vertex incident to u underf.For An normal coloringfofGusingk-colors,ifS(u)≠S(v)for any two different verticesuandvofV(G),thenfis called ak-VDPEC coloring ofG.The min imum number of colors required for a VDPEC coloring ofGis denotedand it is called the VDPEC chromatic numbers ofG.Vertex distinguishing proper edge colorings of the join ofwheelWmand pathPn(n≥3)are studied and the vertex distinguishing edge chromatic numbers of the join ofwheelWmand pathPn(n≥3)are obtained in this paper.

the join of graphs;vertex-distinguishing proper edge coloring;ver-distinguishing proper edge chromatic number

book=9,ebook=358

O 157.5

A

1673-2103(2010)05-0019-05

2010-06-24

王國興(1976-),男,甘肅天水人,講師,碩士,研究方向:圖論及其應(yīng)用.