Wm與Pn(n≤3)聯圖的點可區別邊色數＊

王國興

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

Wm與Pn(n≤3)聯圖的點可區別邊色數＊

王國興

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

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

聯圖;點可區別邊染色;點可區別邊色數

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

1 預備知識

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

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

對圖G,令nk表示度為k的頂點個數,δ≤k≤Δ,設

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

定義[8]設G和H是點不相交且邊不交的簡單圖,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的聯圖.引理1[1]對n≥3的n階完全圖Kn,有

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

2 主要結論

定理1 當m≥3時,

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

情形1 當m=3時,W3∨P1=K5,由引理1知結論成立,即

1)當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種色點可區別正常邊染色.

2)當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 當m≥3時,

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

情形1 當m=3時,W3∨P2=K6,由引理1知結論成立,即

1)當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)當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)當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去染.

因此,上述染色是點可區別正常邊染色,所以m>3當時

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

定理3 當m≥3時,

證明 當m≥3時,有

μ(Wm∨P3)

分以下五種情況考慮.

情形1 當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 當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 當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 當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 當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種色的點可區別正常染色.即有

定理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的點可區別正常邊色數[J].佳木斯大學學報:自然科學版,2010,28(1):144-145.

[7]陳祥恩,張忠輔.K-tn的點可區別正常邊染色[J].數學研究,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-),男,甘肅天水人,講師,碩士,研究方向:圖論及其應用.