外平面圖的距離2-點(diǎn)可區(qū)別邊色數(shù)*

王維凡,王琰雯,黃丹君

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

?

外平面圖的距離2-點(diǎn)可區(qū)別邊色數(shù)*

王維凡,王琰雯,黃丹君

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

邊染色;距離2-點(diǎn)可區(qū)別邊染色;外平面圖;最大度

0 引 言

本文考慮的圖都是有限簡(jiǎn)單圖.設(shè)V(G),E(G),Δ(G),δ(G)分別表示圖G的頂點(diǎn)集、邊集、最大度和最小度.用NG(v)表示與頂點(diǎn)v相鄰的點(diǎn)集合,因此,dG(v)=|NG(v)|是v在圖G中的度.用dG(u,v)表示2個(gè)點(diǎn)u和v在G中的距離,即連接它們的最短路的長(zhǎng)度.在不引起混淆的情況下,分別將Δ(G),NG(v),dG(v),dG(u,v)簡(jiǎn)記為Δ,N(v),d(v),d(u,v).一個(gè)k-點(diǎn)(k+-點(diǎn)或k--點(diǎn))是一個(gè)度數(shù)為k(至多為k,或者至少為k)的點(diǎn).對(duì)i≥1,用ni(v)表示與點(diǎn)v相鄰的i-點(diǎn)的個(gè)數(shù)．若一個(gè)圖G沒(méi)有孤立邊,就稱它是正常的.圖G的一個(gè)正常k-邊染色是指一個(gè)映射φ:E(G)→{1,2,…,k},使得相鄰的邊染不同的顏色.對(duì)于一個(gè)點(diǎn)v∈V(G),用Cφ(v)表示所有與v相關(guān)聯(lián)的邊得到的顏色集合,即Cφ(v)={φ(uv) |uv∈E(G)}.

本文研究外平面圖族的距離2-點(diǎn)可區(qū)別邊染色問(wèn)題,證明了:任意外平面圖G的距離2-點(diǎn)可區(qū)別的邊色數(shù)不超過(guò)2Δ.

1 結(jié)構(gòu)引理

若一個(gè)圖能嵌入到歐幾里得平面上,使得所有點(diǎn)都出現(xiàn)在無(wú)界面的邊界上,則稱這個(gè)圖為外可平面圖.外平面圖是外可平面圖在歐幾里得平面上的一個(gè)嵌入.設(shè)G是一個(gè)外平面圖,用F(G)表示G中面的集合.對(duì)于f∈F(G),用b(f)表示f的邊界,并且若u1,u2,…,un是b(f)上沿順時(shí)針?lè)较虻狞c(diǎn),則記f=[u1u2…un].一個(gè)度為1的頂點(diǎn)也稱為一個(gè)葉子.

為了刻畫(huà)外平面圖的邊-面全色數(shù),王維凡等[11]證明了下面的結(jié)構(gòu)引理：

引理1 設(shè)G是一個(gè)外平面圖,且δ(G)=2,那么G必含有下面子構(gòu)型之一(見(jiàn)圖 1):

1)一條路x1x2x3x4滿足d(x2)=d(x3)=2;

2)一個(gè)3-面[uv1v2]滿足d(u)=2,d(v1)=3;

3)2個(gè)3-面[xu1v1]和[xu2v2]滿足d(u1)=d(u2)=2,d(x)=4.

(a) (b) (c) 圖1 引理1中G的3個(gè)子圖

圖1中,若與一個(gè)點(diǎn)相關(guān)聯(lián)的邊都畫(huà)出來(lái)了,也即這個(gè)點(diǎn)的度數(shù)確定了,就用實(shí)心點(diǎn)來(lái)表示;否則,就用空心點(diǎn)來(lái)表示.

引理2 每一個(gè)至少有2個(gè)頂點(diǎn)的連通圖G必含有下面的子構(gòu)型之一:

1)一個(gè)度數(shù)至多為3的頂點(diǎn)v與葉子相鄰,或者一個(gè)4+-點(diǎn)v至多相鄰于2個(gè)非葉子點(diǎn);

2)一條路x1x2x3x4滿足d(x2)=d(x3)=2;

3)一個(gè)3-面[uv1v2]滿足d(u)=2,d(v1)≥3且n1(v1)=d(v1)-3;

4)2個(gè)3-面[xu1v1]和[xu2v2]滿足d(u1)=d(u2)=2,d(x)≥4和n1(x)=d(x)-4.

證明 采用反證法.假設(shè)G不包含1)～4)中任意一個(gè).因?yàn)镚不含有1),所以G沒(méi)有3--點(diǎn)相鄰于葉子,而且每一個(gè)4+-點(diǎn)v至多與d(v)-3個(gè)葉子相鄰,也就是說(shuō)它至少有3個(gè)鄰點(diǎn)不是葉子.

設(shè)H是由G去掉所有葉子之后得到的圖,那么H是一個(gè)連通的外平面圖.設(shè)v∈V(H),因?yàn)閂(H)?V(G),所以由H的定義可知dG(v)≥2.若2≤dG(v)≤3,則dH(v)=dG(v)≥2;若dG(v)≥4,則dH(v)=dG(v)-n1(v)≥dG(v)-(dG(v)-3)=3.因此,δ(H)=2.由引理1知,H包含圖1 中的子圖形 (a),(b)和(c)之一.注意到：若dH(v)=2,則dG(v)=2.所以,容易觀察到G至少包含引理2中的2),3)和4)之一,與G的假設(shè)相矛盾.引理2證畢.

下面2個(gè)引理是很容易被證明成立的:

引理3 設(shè)Pn是一條長(zhǎng)為n≥2的路,則

引理4 設(shè)Cn是一個(gè)長(zhǎng)為n≥3的圈,則

2 主要結(jié)果

1)G包含一個(gè)3--點(diǎn)v,使得n1(v)≥1;或者G包含一個(gè)4+-點(diǎn) v,使得n1(v)≥k-2,即為引理2中的1).

設(shè)v1,v2,…,vk是v的鄰點(diǎn),其中k=d(v)且v1是G的一個(gè)葉子.下面分為2個(gè)子情形.

②k≥4.那么n1(v)≥k-2.假設(shè)d(vi)=1,i=1,2,…,k-2,且令H=G-{v1,v2,…,vk-2}.則由歸納假設(shè)知,H有一個(gè)應(yīng)用顏色集合C的距離2-點(diǎn)可區(qū)別邊染色φ.不失一般性,設(shè)φ(vvk-1)=1,φ(vvk)=2.注意到點(diǎn)v至多有2Δ-2個(gè)距離為2的點(diǎn).由于

所以一定存在一個(gè)(k-2)-元子集 C′?C{φ(vv1),φ(vv2)},使得vv1,vv2,…,vvk-2可以應(yīng)用集合C′進(jìn)行合法染色.因此,可得到圖G的一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色.

2)G包含一條路x1x2x3x4,使得d(x2)=d(x3)=2,即為引理2中的2).

如果x1與x4重合,那么圖G-x2x3有一個(gè)應(yīng)用顏色集合C的距離2-點(diǎn)可區(qū)別邊染色φ.由于x2x3有2個(gè)禁用色,且x2,x3至多有Δ-2個(gè)距離為2的頂點(diǎn),|C|=2Δ,因此可以對(duì)x2x3進(jìn)行合法染色,從而得到圖G的一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色.

下面假設(shè)x1≠x4.設(shè)H是由圖G通過(guò)收縮邊x2x3成為一個(gè)新點(diǎn)w后而得到的圖,那么H是一個(gè)滿足|T(H)|<|T(G)|的簡(jiǎn)單外平面圖.由歸納假設(shè),H有一個(gè)應(yīng)用顏色集合C的距離2點(diǎn)可區(qū)別邊染色φ,使得φ(wx1)=1且φ(wx4)=2.基于φ,在圖G中,把x1x2染成顏色1,把x3x4染成顏色2.若x2x3不能被合法染色,則d(x1)=d(x4)=Δ,Cφ(yi)={1,2+i},i=1,2,…,Δ-1,且Cφ(zj)={2,Δ+1+j},j=1,2,…,Δ-1,其中y1,y2,…,yΔ-1是x1的不同于x2的鄰點(diǎn),z1,z2,…,zΔ-1是x4的不同于x3的鄰點(diǎn).因此,φ(x1yi)=2+i 且φ(x4zj)=Δ+1+j.把x1x2改染成2,把x2x3染成1,由此就得到圖G的一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色.

3)G包含一個(gè)3-面[uv1v2]滿足d(u)=2,d(v1)=k≥3和n1(v1)=k-3,即為引理2中的3).

基于2)的證明,可以假設(shè)d(v2)≥3.設(shè)u,w,v2,x1,x2,…,xk-3是v1的鄰點(diǎn),其中d(x1)=d(x2)=…=d(xk-3)=1.下面分為2種子情形.

①k≥4.設(shè)H=G-{x1,x2,…,xk-3}.由歸納假設(shè)知,H有一個(gè)應(yīng)用顏色集合C的距離2-點(diǎn)可區(qū)別邊染色φ,使得φ(wv1)=1,φ(v1v2)=2及φ(uv1)=3.注意到v1至多有(Δ-1)+(Δ-2)=2Δ-3個(gè)距離為2的k-點(diǎn).若k≥5,則由

知,一定存在一個(gè)(k-3)-元子集C′?{4,5,…,2Δ},使得v1x1,v1x2,…,v1xk-3可以應(yīng)用顏色集合C′進(jìn)行合法染色,這樣就得到了圖G的一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色.因此,下面假設(shè)k=4.若v1x1不能夠被合法染色,那么對(duì)所有的i=4,5,…,2Δ,{1,2,3,i}是v1的某個(gè)距離為2且度數(shù)為4的頂點(diǎn)的顏色集合.所以,v1的所有距離為2的點(diǎn)都是4-點(diǎn).在{4,5}{φ(uv2)}中選取一個(gè)顏色來(lái)改染v1u,然后把v1x1染成顏色6即可.

②k=3.令 H=G-uv1.由歸納假設(shè)知,H有一個(gè)應(yīng)用顏色集合C的距離2-點(diǎn)可區(qū)別邊染色φ,使得φ(uv2)=1,φ(v1v2)=2和φ(wv1)=a.先設(shè)d(w)=2.若a=1,則u和v1總共至多有Δ個(gè)距離為2的點(diǎn).因?yàn)棣ぁ?且|C{1,2}|=2Δ-2>Δ,所以可以在C{1,2}中選取一個(gè)顏色對(duì)uv1進(jìn)行合法染色.若 a≠1,不妨設(shè)a=3,則只要用{4,5,2Δ}給邊uv1正常染色,u與w的顏色集合就不同.故u和v1總共至多有Δ-1個(gè)距離為2的點(diǎn).因?yàn)棣ぁ?且|C{1,2,3}|=2Δ-3>Δ-1,所以可以在C{1,2,3}中選取一個(gè)顏色對(duì)uv1進(jìn)行合法染色.這樣就得到了圖G一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色.

現(xiàn)在,假設(shè)d(w)≥3,那么在圖G中,u和v1總共至多有(Δ-1)+(Δ-2)=2Δ-3個(gè)沖突點(diǎn).若a=1,則|C{1,2}|=2Δ-2>2Δ-3,可以在C{1,2}中選取一個(gè)顏色對(duì)uv1進(jìn)行合法染色.所以,下面假設(shè)a≠1,不妨設(shè)a=3.若 uv1不能夠被合法染色,則假設(shè){{2,3,i} | i=4,5,…,Δ+2}={Cφ(x)|x∈N(w){v1}},且{2,3,j}或{1,j}(j=Δ+3,Δ+4,…,2Δ)是v2的某些鄰點(diǎn)的顏色集合.在這種情況下,把uv2和v1v2的顏色互換,把uv1染成顏色4即可.

4)G包含2個(gè)3-面[xu1v1]和[xu2v2]滿足d(u1)=d(u2)=2,d(x)=k≥4和n1(x)=k-4,即為引理2中的4).

基于2)的證明,可以假設(shè)d(v1)≥3且d(v2)≥3.設(shè)y1,y2,…,yd(v1)-2是v1的不同于x和u1的鄰點(diǎn),z1,z2,…,zd(v2)-2是v2的不同于x和u2的鄰點(diǎn).同時(shí),用x1,x2,…,xk-4表示x的不同于u1,u2,v1,v2的鄰點(diǎn).由定義知,對(duì)所有的i=1,2,…,k-4,都有d(xi)=1.需要討論下面2種可能性:

①k≥5.設(shè)H=G-{x1,x2,…,xk-4}.由歸納假設(shè)知,H有一個(gè)應(yīng)用顏色集合C的距離2-點(diǎn)可區(qū)別邊染色φ,使得φ(xv1)=1,φ(xu1)=2,φ(xu2)=3及φ(xv2)=4.注意到x至多有2(Δ-2)=2Δ-4個(gè)距離為2的k-點(diǎn).若k≥6,則由

知,存在一個(gè)(k-4)-元子集C′?C{1,2,3,4},使得xx1,xx2,…,xxk-4可以使用顏色集合C′進(jìn)行合法染色.因此,下面假設(shè)k=5.若 xx1不能夠被合法染色,則d(v1)=d(v2)=Δ,且對(duì)每一個(gè)i=5,6,…,2Δ,{1,2,3,4,i}是{y1,y2,…,yΔ-2,z1,z2,…,zΔ-2}中的一個(gè)頂點(diǎn)的顏色集合,這就意味著{y1,y2,…,yΔ-2,z1,z2,…,zΔ-2}中的每一個(gè)點(diǎn)都是5-點(diǎn).為了得到圖G的一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色,只需在{5,6}{φ(v1u1)}中選取一個(gè)顏色改染xu1,然后把xx1染成顏色7即可.

②k=4.由歸納假設(shè)知,G-xu1有一個(gè)應(yīng)用顏色集合C的距離2-點(diǎn)可區(qū)別邊染色φ,使得φ(xv1)=1,φ(xu2)=2,φ(xv2)=3,φ(u1v1)=a.注意到a≠1,因此,需要考慮下面2種情況.

i)a∈{2,3}.

易見(jiàn),x和u1在圖G中總共至多有2Δ-3 個(gè)沖突點(diǎn).若xu1不能夠被合法染色,則d(v1)=d(v2)=Δ.進(jìn)而進(jìn)一步假設(shè):Cφ(u2)={2,4};Cφ(zi)={1,2,3,i+4},i=1,2,…,Δ-2;Cφ(yi)={a,i+Δ+2}或者{1,2,3,i+Δ+2},i=1,2,…,Δ-2.所以φ(u2v2)=4.互換u2v2和xv2的顏色,然后把xu1染成顏色5,就得到了圖G的一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色.

ii)a?{2,3},令 a=4.

若xu1能夠被正常染色,則u1和u2將得到不同的顏色集合.此外,x和u1在圖G中總共至多有2Δ-4個(gè)沖突點(diǎn).若xu1不能夠被合法染色,則推出d(v1)=d(v2)=Δ,且可以假設(shè)Cφ(zi)={1,2,3,i+4},i=1,2,…,Δ-2;Cφ(yi)={a,i+Δ+2}或者{1,2,3,i+Δ+2},i=1,2,…,Δ-2.這時(shí)可以把u1v1和xv1的顏色互換,然后把xu1染成顏色5,就得到了G的一個(gè)距離2-點(diǎn)可區(qū)別2Δ-邊染色.定理1證畢.

[1]Akbari S,Bidkhori N,Nosrati N.r-Strong edge colorings of graphs[J].Discrete Math,2006,306(23):3005-3010.

[2]Zhang Zhongfu,Li Jingwen,Chen Xiangen,et al.D(β)-vertex-distinguishing proper edge-coloring of graphs[J].Acta Math Sinica:Chin Ser,2006,49(3):703-708.

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

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

[7]Zhang Zhongfu,Liu Linzhong,Wang Jianfang.Adjacent strong edge coloring of graphs[J].Appl Math Lett,2002,15(5):623-626.

[8]Balister P N,Gy?ri E,Lehel J,et al.Adjacent vertex distinguishing edge-colorings[J].SIAM J Discrete Math,2007,21(1):237-250.

[9]Hatami H.Δ+300 is a bound on the the adjacent vertex distinguishing edge chromatic number[J].J Combin Theory Ser B,2005,95(2):246-256.

[10]Horňák M,Huang Danjun,Wang Weifan.On neighbor-distinguishing index of planar graphs[J].J Graph Theory,2014,76(4):262-278.

[11]Wang Weifan,Zhang Kemin.Δ-matchings and edge-face chromatic numbers[J].Acta Math Appl Sin,1999,22(2):236-242.

(責(zé)任編輯 陶立方)

Distance vertex-distinguishing index of outerplanar graphs

WANG Weifan,WANG Yanwen,HUANG Danjun

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

edgecoloring; 2-distance vertex-distinguishing index; outerplanar graph; maximum degree

10.16218/j.issn.1001-5051.2016.01.001

??2015-05-27；

2015-09-02

國(guó)家自然科學(xué)基金資助項(xiàng)目(11371328;11301486)

王維凡(1955-)，男，遼寧沈陽(yáng)人，教授，博導(dǎo).研究方向：圖論與組合優(yōu)化.

O157.5

A

1001-5051(2016)01-001-05