不含5-圈和6-圈的平面圖的(2,1)-全標號

呂蕭,孫磊

(山東師范大學數學與統計學院,山東 濟南 250014)

1 引言

頻道分配問題是指將電波頻率分配給各個傳輸站,為避免信號干擾,如果兩個站點距離非常近,則分配給它們的頻率至少要相差2,若兩個站點距離較近,但不是非常近,則分配給它們的頻率只要不同即可.受此問題啟發,Griggs和 Yeh[1]引入了L(2,1)-標號,它的自然推廣是L(p,1)-標號[2].Whittesey[3]等人研究了圖G的剖分圖的L(2,1)-標號.圖G的剖分圖s1(G)是在圖G的每條邊上插入一個點得到的圖.圖s1(G)的L(p,1)-標號對應原圖G的一個(p,1)-全標號.圖G的k-(p,1)-全標號是對圖G的頂點和邊的一個標號分配,即存在映射f:V(G)∪E(G)→{0,1,···,k},使得

(1)G中任意相鄰兩點u,v,有|f(u)?f(v)|≥1;

(2)G中任意相鄰兩邊e,e′,有|f(e)?f(e′)|≥1;

(3)G中任意相關聯的點u和邊e,有|f(u)?f(e)|≥p.

稱這樣的一個分配為圖G的(p,1)-全標號.(p,1)-全標號的跨度為任意兩個標號的最大差值.圖G的所有(p,1)-全標號的最小跨度稱為(p,1)-全標號數,記作λTp(G).本文中未說明的定義和符號與文獻[4]中一致.另外,本文不考慮標號和顏色的區別.

由此可見,圖的(p,1)-全標號是加強了條件的全染色問題,即還要求任意一點與其關聯邊的標號至少相差p.不難看出,圖G的(1,1)-全標號恰是圖G的全染色,故λT1(G)=χ′′(G)?1,其中χ′′(G) 是全色數.

文獻 [5]研究了λTp(G)的上界,證明了λTp(G)≤2?(G)+p?1.但對最大度較大的圖,這個上界并不是緊的.于是,他們給出了猜想:

猜想 1.1[5]λTp(G)≤min{?(G)+2p?1,2?(G)+p?1}.

當p=1時,這個猜想即全染色猜想.

文獻[5]利用圖的最大割證明了

并改進了(2,1)-全標號的某些結果:

若 ?(G)≥5是奇數,則λT2(G)≤2?(G)?1;

若 ?(G)≥2,則λT2(G)≤2?(G);

若 ?=2,則λT2(G)=4;

若 ?(G)≤3,則λT2(G)≤6.

對于平面圖,當最大度較小時文獻[6]證明了:

若 ?≤3，圍長g≥18,則λT2(G)≤5;

若?≤4，圍長g≥12,則λT2(G)≤7.本文討論了最大度為6、7、8的圖,如果不含5-圈和 6-圈,λT2(G)=2??p.

2 主要結果及其證明

定理 2.1若G為連通平面圖,?(G)=p+5,且G不包含5-圈和6-圈,則

假設G=(V,E)為點數加邊數最小的反例,即?(G)=p+5,且G不包含5-圈和6-圈,而λT2(G)>2??p.且G的每一個真子圖都能用2??p+1種顏色得到(2,1)-全標號.因為G不包含5-圈和6-圈,所以我們有下列觀察:

(O1)v是一個4+-點,如果v關聯著一個3-面,那么v至少關聯2個7+-面;

(O2)每一個k-點(k≥4)至多關聯(k-2)個3-面;

(O3)如果一個4-面f與一個4-面相鄰,那么f與f′交于一條長為2的路,路上點的度數為?,2,?.也就是說如果δ(f)≥3,那么與f相鄰的面都是7+面.

G有以下結構性質:

(a)對每條邊e=uv∈E,min{d(u),d(v)}≤??/2?,有d(u)+d(v)≥?+2;

(b)G不含偶圈v1v2v3···v2tv1,使得d(v1)=d(v3)=···=d(v2t?1)=2;

(c)如果最大度點v關聯兩個2-點v1、v2,那么v1和v2都不關聯3-面;

(d)G不包含下圖中的構型,分別為圖1中的(1)、(2)、(3)、(4).其中黑色點除在下圖中的鄰點外無其他鄰點,在圖(1)和(2)中d(v)=??1,在圖(3)和(4)中d(v)=??1.

圖1 G的構型圖

證明(a)假設有一條邊uv∈E,使得d(u)≤?/2,d(u)+d(v)≤?+1,由G的極小性,G?e可用p+11種顏色得到一個(2,1)-全標號.現擦去點u的顏色.記此時的G的部分(2,1)-全標號為Φ.現在染點u和邊uv.對點u,至少有

種選擇,則可將u染好.對邊uv,至少有

種選擇,因此可以將Φ拓展到G上,得到矛盾.

(b)假設G有偶圈

由G的極小性,可用p+11種顏色得到G{v1,v3,···,v2t?1}的一個 (2,1)-全標號,為了染好C上的每條邊,對每條邊,至少有

種顏色可選擇,現在染好C上的邊.對C上的每個2-點,至少有

種顏色選擇,從而將G?C的(2,1)-全標號拓展到G上,得到矛盾.

(c)設d(v)=6,d(v1)=d(v2)=2,v1關聯一個3-面,現由G的極小性,可用p+11種顏色得到G-u1v1的一個(2,1)-全標號.現擦去v1和v2的顏色.將此時的G的部分(2,1)-全標號記作Φ.考慮邊u1v1,由u1v1的鄰邊和關聯的點,至少有

種顏色選擇.把邊u1v1染好.對于點v1、v2各自至少有

種顏色可供選擇.從而將Φ拓展到G上,得到G的p+11種顏色的(2,1)-全標號,得到矛盾.

(d)情形 1設d(v)=??1,d(u)=d(w)=3.由G的極小性,可用p+11種顏色得到H=G{uv,wv}的一個(2,1)-全標號,擦去點u和w的顏色.記此時的G的部分(2,1)-全標號為Φ.記AΦ(x)為x的可用顏色集,x∈V(G)∪E(G).下文中都用此記號來記可用顏色集.現在先來染點w和邊vw.對點w,至少有p+11?(3+2×3)≥3種顏色可供選擇.對邊wv,至少有

種顏色選擇.現在將點w和邊wv染好.

下面討論點u和邊uv.對點u至少有

種顏色可供選擇,對邊uv至少有

種顏色可供選擇.選擇α∈AΦ(u)來染點u.如果

那么可以選擇γ∈AΦ(uv){α?1,α,α+1}染好邊uv;否則

那么可以選擇AΦ(u)中除α之外的兩種顏色之一β去染u.因為

可選擇γ′∈AΦ(uv){β?1,β,β+1}來染邊uv.從而將Φ拓展到了G上,得到p+11種顏色的G的(2,1)-全標號,矛盾.

情形 2設d(v)=??1,d(u)=d(w)=3.由G的極小性,可用p+11種顏色得到H=G{uv,wv}的一個(2,1)-全標號,擦去點u和w的顏色.記此時的G的部分(2,1)-全標號為Φ.現在先來染點w和邊vw.對點w,至少有

種顏色可供選擇.對邊wv,至少有

種顏色可供選擇.現在將點w和邊wv染好.

下面討論點u和邊uv.對點u至少有

種顏色可供選擇,對邊uv至少有

種顏色可供選擇.選擇α∈AΦ(u)來染點u.如果

那么可以選擇γ∈AΦ(uv){α?1,α,α+1}染好邊uv;否則

那么可以選擇且β∈AΦ(u)去染u.因為

故可選擇γ′∈AΦ(uv){β?1,β,β+1}來染邊uv.從而得到Φ在G上的拓展,即p+11種顏色的G的(2,1)-全標號,得到矛盾.

情形3設d(v)=?,d(u)=3d(w)=2.由G的極小性,可用p+11種顏色得到H=G?uv的一個(2,1)-全標號,擦去點u和w的顏色.用Φ記此時的G的部分(2,1)-全標號.現在先來染點w.對點w,至少有

種顏色可供選擇,將點w染好.現在討論點u和邊uv,對點u,至少有

種顏色可供選擇,對邊uv至少有

種顏色可供選擇.選擇α∈AΦ(uv)來染邊uv.如果

那么可以選擇γ∈AΦ(u){α?1,α,α+1}染好u;否則

那么可以選擇β∈AΦ(uv){α}去染uv.又因為

可選擇γ′∈AΦ(u){β?1,β,β+1}來染點u.從而得到 Φ在G上的拓展,即p+11種顏色的G的(2,1)-全標號,矛盾.

情形4設d(v)=?,d(u)=3d(w)=2.由G的極小性,可用p+11種顏色得到H=G?uv的一個(2,1)-全標號,擦去點u和w的顏色.用Φ記此時的G的部分(2,1)-全標號.現在先來染點w.對點w,至少有

種顏色可供選擇,將點w染好.現在討論點u和邊uv,對點u,至少有

種顏色選擇.對邊uv至少有

種顏色可供選擇.選擇α∈AΦ(uv)來染邊uv.如果

那么可以選擇γ∈AΦ(u){α?1,α,α+1}染好u;否則

那么可以選擇β∈AΦ(uv){α}去染uv.又因為

故可選擇γ′∈AΦ(u){β?1,β,β+1}來染點u.從而得到 Φ在G上的拓展,即p+11種顏色的G的(2,1)-全標號,矛盾.

G是平面圖,由歐拉公式|V(G)|?|E(G)|+|F(G)|=2,有

定義原始權值,?x∈V(G),w(x)=2d(x)?6.?x∈F(G),w(x)=d(x)?6.由上式知權值總和為?12.下面根據權值轉移規則,則給每個x∈V∪F分配新權值w′(x).權值規則不會影響總和.所以

下面來證?x∈V∪F,w′(x)≥0得到矛盾.權值轉移規則如下:

(R1)每個2-點從它的每個鄰點接收1.

(R2)每個4+-點給每個關聯的4-面1.

(R3)每個4-點給每個關聯的3-面1.

(R4)每個5+-點給每個關聯的3-面如果δ(f)≤3;否則,給 1.

現在驗證?x∈V∪F,w′(x)≥0:

設f為G中任意一個面.

如果d(f)≥7,顯然w′(f)=w(f)≥0.

如果d(f)=4,顯然w(f)=?2.由結構性質(a),f至少關聯2個4+-點,

如果d(f)=3,顯然w(f)=?3.由結構性質(a),f關聯3個4+-點或至少關聯2個5+-點,

設v為G中任意一個頂點.

如果d(v)=2,w′(v)=w(v)+1×2=0.

如果d(v)=3,w′(v)=w(v)=0.

如果d(v)=4,w(v)=2,由結構性質(a),v的鄰居都是4+-點,由觀察(O1)和(O3),v至多關聯 2個 7?-面,w′(v)≥2?2×1=0.

如果d(v)=??1=p+4(p=1,2,3),初始權值w(v)=2p+2,而且由結構性質(a),v的鄰居都是3+-點(a).若v關聯一個3-面f,由觀察(O1),那么v至少關聯兩個7+-面.如果δ(f)=3,那么由結構性質(d),n3(v)=1,即至多有一個3-面從v處接收

否則v給關聯的面p+2,w′(v)=2p+2?(p+2)=p>0;若v關聯的都是 4+-面,因為G不含5-和6-圈,所以v至多關聯p+1個4-面,

如果

初始權值w(v)=2p,由結構性質(a),v的鄰居都是4+-點,因為G不含5-圈和6-圈，v至多關聯p+1個 7?-面,w′(v)≥2p?(p+1)=p?1>0.

如果

初始權值w(v)=2p?2,由結構性質 (a),v的鄰居都是 5+-點,v至多關聯p個 7?-面,w′(v)≥2p?2?p=p?2>0.

如果

若v關聯的鄰居都是3+-點,由觀察(O1),v至多關聯(??2)=p+3個從v點接收的3-面,否則考慮與v關聯的2-點的個數n2(v).

如果n2(v)=1,由觀察 (O1)和(O3),v至多關聯 (??2)=p+3個4?-面,由性質 (d)其中至多有(p+1)個從v點接收的3-面,

如果n2(v)=2,由觀察(O3)和結構性質(b)(c),p=1(?=6)時,v會關聯2個3-面,至多p個4-面或1個3-面,至多(p+1)個4-面或不關聯3-面,至多(p+3)個4-面,此時

p=2(?=7)時,v會關聯3個 3-面,至多(p?1)個4-面或2個 3-面,至多p個4-面或1個 3-面,至多(p+1)個4-面或不關聯 3-面,至多(p+3)個4-面,

p=3(?=8)時,v會至多關聯4個3-面,不關聯4-面或關聯3個3-面,至多(p?1)個4-面或2個3-面,至多p個4-面或1個3-面,至多(p+1)個4-面或不關聯3-面,至多(p+3)個 4-面,

如果n2(v)=3,由觀察 (O3)和結構性質(b)(c),p=1(?=6)時,v會關聯 2個 3-面,至多p?1個4-面或1個 3-面,至多p個4-面或不關聯3-面,至多(p+2)個 4-面,

p=2(?=7)時,情況與p=1(?=6)時相同,此時

p=3(?=8)時,v會關聯3個 3-面,至多 (p?2)個 4-面或 2個 3-面,至多p?1個4-面或 1個3-面,至多p個4-面或不關聯3-面,至多(p+2)個4-面;

如果n2(v)=4,由觀察(O3)和結構性質(b)(c),p=1(?=6)時,v會關聯1個3-面,至多p?1個4-面或不關聯3-面,至多(p+1)個 4-面;

p=2(?=7)時情況與p=1(?=6)時相同,此時

p=3(?=8)時,v會關聯 2個3-面,至多p?2個4-面或 1個3-面,至多p?1個4-面或不關聯 3-面,至多(p+1)個4-面,從而

如果n2(v)=5,由觀察(O3)和結構性質(b)(c),p=1(?=6)時,v不關聯3-面,至多p個 4-面;此時

p=2(?=7)時,v會關聯1個3-面,至多p?2個4-面或不關聯3-面,至多p個4-面,此時

p=3(?=8)時,v會關聯 2個3-面,至多p?3個4-面或 1個3-面,至多p?2個4-面或不關聯 3-面,至多p個4-面.此時

如果n2(v)=6,由觀察(O3)和結構性質(b)(c),p=1(?=6)時,v既不關聯3-面也不關聯4-面,此時

p=2(?=7)時,v不關聯 3-面,至多 (p?1)個 4-面,此時

p=3(?=8)時,v會關聯1個 3-面,至多(p?3)個4-面或不關聯3-面,至多 (p?1)個4-面,此時

特別地,?=7、8時,情況如下:

如果n2(v)=7,由觀察(O3)和結構性質(b)(c),p=2(?=7)時,v既不關聯3-面也不關聯4-面,此時

p=3(?=8)時,v不關聯3-面,至多(p?2)個4-面.此時

如果n2(v)=8,p=3即?=8時,v既不關聯3-面也不關聯4-面.此時

于是移值后,在任何一種情況下,對每個元素x∈V(G)∪F(G),有w′(x)≥0,所有點數值和這與矛盾,從而完成定理1的證明.

[1]Griggs J R,Yeh R K.Labeling graphs with a condition at distance two[J].SIAM J.Discrete Math.,1992,5:586-595.

[2]Chang G J,Ke W T,Kuo D,et al.On L(d,1)-labeling of graphs[J].Discrete Math.,2000,220:57-66.

[3]Whittlesey M A,Georges J R,Mauro D W.On theλ-number ofQnand related graphs[J].SIAM J.Discrete Math.,1995,8:449-506.

[4]Yu Y,Zhang X,Wang G,et al.(2,1)-Total labeling of planar graphs with large maximum degree[J].Computer Science,2011,26(1):53-59.

[5]Havet F,Yu M L.(p,1)-Total labeling of graphs[J].Discrete Mathematics,2008,308(4):496-513.

[6]Sun Lei,Li Haiying.(2,1)-Total labeling of planar graphs with large girth and low degree[J].Ars Combinatoria,2011,100:65-72.