呂蕭,孫磊

(山東師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,山東 濟(jì)南 250014)

1 引言

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

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

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

(3)G中任意相關(guān)聯(lián)的點(diǎn)u和邊e,有|f(u)?f(e)|≥p.

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

由此可見(jiàn),圖的(p,1)-全標(biāo)號(hào)是加強(qiáng)了條件的全染色問(wèn)題,即還要求任意一點(diǎn)與其關(guān)聯(lián)邊的標(biāo)號(hào)至少相差p.不難看出,圖G的(1,1)-全標(biāo)號(hào)恰是圖G的全染色,故λT1(G)=χ′′(G)?1,其中χ′′(G) 是全色數(shù).

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

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

當(dāng)p=1時(shí),這個(gè)猜想即全染色猜想.

文獻(xiàn)[5]利用圖的最大割證明了

并改進(jìn)了(2,1)-全標(biāo)號(hào)的某些結(jié)果:

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

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

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

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

對(duì)于平面圖,當(dāng)最大度較小時(shí)文獻(xiàn)[6]證明了:

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

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

2 主要結(jié)果及其證明

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

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

(O1)v是一個(gè)4+-點(diǎn),如果v關(guān)聯(lián)著一個(gè)3-面,那么v至少關(guān)聯(lián)2個(gè)7+-面;

(O2)每一個(gè)k-點(diǎn)(k≥4)至多關(guān)聯(lián)(k-2)個(gè)3-面;

(O3)如果一個(gè)4-面f與一個(gè)4-面相鄰,那么f與f′交于一條長(zhǎng)為2的路,路上點(diǎn)的度數(shù)為?,2,?.也就是說(shuō)如果δ(f)≥3,那么與f相鄰的面都是7+面.

G有以下結(jié)構(gòu)性質(zhì):

(a)對(duì)每條邊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)如果最大度點(diǎn)v關(guān)聯(lián)兩個(gè)2-點(diǎn)v1、v2,那么v1和v2都不關(guān)聯(lián)3-面;

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

圖1 G的構(gòu)型圖

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

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

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

(b)假設(shè)G有偶圈

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

種顏色可選擇,現(xiàn)在染好C上的邊.對(duì)C上的每個(gè)2-點(diǎn),至少有

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

(c)設(shè)d(v)=6,d(v1)=d(v2)=2,v1關(guān)聯(lián)一個(gè)3-面,現(xiàn)由G的極小性,可用p+11種顏色得到G-u1v1的一個(gè)(2,1)-全標(biāo)號(hào).現(xiàn)擦去v1和v2的顏色.將此時(shí)的G的部分(2,1)-全標(biāo)號(hào)記作Φ.考慮邊u1v1,由u1v1的鄰邊和關(guān)聯(lián)的點(diǎn),至少有

種顏色選擇.把邊u1v1染好.對(duì)于點(diǎn)v1、v2各自至少有

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

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

種顏色選擇.現(xiàn)在將點(diǎn)w和邊wv染好.

下面討論點(diǎn)u和邊uv.對(duì)點(diǎn)u至少有

種顏色可供選擇,對(duì)邊uv至少有

種顏色可供選擇.選擇α∈AΦ(u)來(lái)染點(diǎn)u.如果

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

那么可以選擇AΦ(u)中除α之外的兩種顏色之一β去染u.因?yàn)?/p>

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

情形 2設(shè)d(v)=??1,d(u)=d(w)=3.由G的極小性,可用p+11種顏色得到H=G{uv,wv}的一個(gè)(2,1)-全標(biāo)號(hào),擦去點(diǎn)u和w的顏色.記此時(shí)的G的部分(2,1)-全標(biāo)號(hào)為Φ.現(xiàn)在先來(lái)染點(diǎn)w和邊vw.對(duì)點(diǎn)w,至少有

種顏色可供選擇.對(duì)邊wv,至少有

種顏色可供選擇.現(xiàn)在將點(diǎn)w和邊wv染好.

下面討論點(diǎn)u和邊uv.對(duì)點(diǎn)u至少有

種顏色可供選擇,對(duì)邊uv至少有

種顏色可供選擇.選擇α∈AΦ(u)來(lái)染點(diǎn)u.如果

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

那么可以選擇且β∈AΦ(u)去染u.因?yàn)?/p>

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

情形3設(shè)d(v)=?,d(u)=3d(w)=2.由G的極小性,可用p+11種顏色得到H=G?uv的一個(gè)(2,1)-全標(biāo)號(hào),擦去點(diǎn)u和w的顏色.用Φ記此時(shí)的G的部分(2,1)-全標(biāo)號(hào).現(xiàn)在先來(lái)染點(diǎn)w.對(duì)點(diǎn)w,至少有

種顏色可供選擇,將點(diǎn)w染好.現(xiàn)在討論點(diǎn)u和邊uv,對(duì)點(diǎn)u,至少有

種顏色可供選擇,對(duì)邊uv至少有

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

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

那么可以選擇β∈AΦ(uv){α}去染uv.又因?yàn)?/p>

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

情形4設(shè)d(v)=?,d(u)=3d(w)=2.由G的極小性,可用p+11種顏色得到H=G?uv的一個(gè)(2,1)-全標(biāo)號(hào),擦去點(diǎn)u和w的顏色.用Φ記此時(shí)的G的部分(2,1)-全標(biāo)號(hào).現(xiàn)在先來(lái)染點(diǎn)w.對(duì)點(diǎn)w,至少有

種顏色可供選擇,將點(diǎn)w染好.現(xiàn)在討論點(diǎn)u和邊uv,對(duì)點(diǎn)u,至少有

種顏色選擇.對(duì)邊uv至少有

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

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

那么可以選擇β∈AΦ(uv){α}去染uv.又因?yàn)?/p>

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

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

定義原始權(quán)值,?x∈V(G),w(x)=2d(x)?6.?x∈F(G),w(x)=d(x)?6.由上式知權(quán)值總和為?12.下面根據(jù)權(quán)值轉(zhuǎn)移規(guī)則,則給每個(gè)x∈V∪F分配新權(quán)值w′(x).權(quán)值規(guī)則不會(huì)影響總和.所以

下面來(lái)證?x∈V∪F,w′(x)≥0得到矛盾.權(quán)值轉(zhuǎn)移規(guī)則如下:

(R1)每個(gè)2-點(diǎn)從它的每個(gè)鄰點(diǎn)接收1.

(R2)每個(gè)4+-點(diǎn)給每個(gè)關(guān)聯(lián)的4-面1.

(R3)每個(gè)4-點(diǎn)給每個(gè)關(guān)聯(lián)的3-面1.

(R4)每個(gè)5+-點(diǎn)給每個(gè)關(guān)聯(lián)的3-面如果δ(f)≤3;否則,給 1.

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

設(shè)f為G中任意一個(gè)面.

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

如果d(f)=4,顯然w(f)=?2.由結(jié)構(gòu)性質(zhì)(a),f至少關(guān)聯(lián)2個(gè)4+-點(diǎn),

如果d(f)=3,顯然w(f)=?3.由結(jié)構(gòu)性質(zhì)(a),f關(guān)聯(lián)3個(gè)4+-點(diǎn)或至少關(guān)聯(lián)2個(gè)5+-點(diǎn),

設(shè)v為G中任意一個(gè)頂點(diǎn).

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

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

如果d(v)=4,w(v)=2,由結(jié)構(gòu)性質(zhì)(a),v的鄰居都是4+-點(diǎn),由觀察(O1)和(O3),v至多關(guān)聯(lián) 2個(gè) 7?-面,w′(v)≥2?2×1=0.

如果d(v)=??1=p+4(p=1,2,3),初始權(quán)值w(v)=2p+2,而且由結(jié)構(gòu)性質(zhì)(a),v的鄰居都是3+-點(diǎn)(a).若v關(guān)聯(lián)一個(gè)3-面f,由觀察(O1),那么v至少關(guān)聯(lián)兩個(gè)7+-面.如果δ(f)=3,那么由結(jié)構(gòu)性質(zhì)(d),n3(v)=1,即至多有一個(gè)3-面從v處接收

否則v給關(guān)聯(lián)的面p+2,w′(v)=2p+2?(p+2)=p>0;若v關(guān)聯(lián)的都是 4+-面,因?yàn)镚不含5-和6-圈,所以v至多關(guān)聯(lián)p+1個(gè)4-面,

如果

初始權(quán)值w(v)=2p,由結(jié)構(gòu)性質(zhì)(a),v的鄰居都是4+-點(diǎn),因?yàn)镚不含5-圈和6-圈，v至多關(guān)聯(lián)p+1個(gè) 7?-面,w′(v)≥2p?(p+1)=p?1>0.

如果

初始權(quán)值w(v)=2p?2,由結(jié)構(gòu)性質(zhì) (a),v的鄰居都是 5+-點(diǎn),v至多關(guān)聯(lián)p個(gè) 7?-面,w′(v)≥2p?2?p=p?2>0.

如果

若v關(guān)聯(lián)的鄰居都是3+-點(diǎn),由觀察(O1),v至多關(guān)聯(lián)(??2)=p+3個(gè)從v點(diǎn)接收的3-面,否則考慮與v關(guān)聯(lián)的2-點(diǎn)的個(gè)數(shù)n2(v).

如果n2(v)=1,由觀察 (O1)和(O3),v至多關(guān)聯(lián) (??2)=p+3個(gè)4?-面,由性質(zhì) (d)其中至多有(p+1)個(gè)從v點(diǎn)接收的3-面,

如果n2(v)=2,由觀察(O3)和結(jié)構(gòu)性質(zhì)(b)(c),p=1(?=6)時(shí),v會(huì)關(guān)聯(lián)2個(gè)3-面,至多p個(gè)4-面或1個(gè)3-面,至多(p+1)個(gè)4-面或不關(guān)聯(lián)3-面,至多(p+3)個(gè)4-面,此時(shí)

p=2(?=7)時(shí),v會(huì)關(guān)聯(lián)3個(gè) 3-面,至多(p?1)個(gè)4-面或2個(gè) 3-面,至多p個(gè)4-面或1個(gè) 3-面,至多(p+1)個(gè)4-面或不關(guān)聯(lián) 3-面,至多(p+3)個(gè)4-面,

p=3(?=8)時(shí),v會(huì)至多關(guān)聯(lián)4個(gè)3-面,不關(guān)聯(lián)4-面或關(guān)聯(lián)3個(gè)3-面,至多(p?1)個(gè)4-面或2個(gè)3-面,至多p個(gè)4-面或1個(gè)3-面,至多(p+1)個(gè)4-面或不關(guān)聯(lián)3-面,至多(p+3)個(gè) 4-面,

如果n2(v)=3,由觀察 (O3)和結(jié)構(gòu)性質(zhì)(b)(c),p=1(?=6)時(shí),v會(huì)關(guān)聯(lián) 2個(gè) 3-面,至多p?1個(gè)4-面或1個(gè) 3-面,至多p個(gè)4-面或不關(guān)聯(lián)3-面,至多(p+2)個(gè) 4-面,

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

p=3(?=8)時(shí),v會(huì)關(guān)聯(lián)3個(gè) 3-面,至多 (p?2)個(gè) 4-面或 2個(gè) 3-面,至多p?1個(gè)4-面或 1個(gè)3-面,至多p個(gè)4-面或不關(guān)聯(lián)3-面,至多(p+2)個(gè)4-面;

如果n2(v)=4,由觀察(O3)和結(jié)構(gòu)性質(zhì)(b)(c),p=1(?=6)時(shí),v會(huì)關(guān)聯(lián)1個(gè)3-面,至多p?1個(gè)4-面或不關(guān)聯(lián)3-面,至多(p+1)個(gè) 4-面;

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

p=3(?=8)時(shí),v會(huì)關(guān)聯(lián) 2個(gè)3-面,至多p?2個(gè)4-面或 1個(gè)3-面,至多p?1個(gè)4-面或不關(guān)聯(lián) 3-面,至多(p+1)個(gè)4-面,從而

如果n2(v)=5,由觀察(O3)和結(jié)構(gòu)性質(zhì)(b)(c),p=1(?=6)時(shí),v不關(guān)聯(lián)3-面,至多p個(gè) 4-面;此時(shí)

p=2(?=7)時(shí),v會(huì)關(guān)聯(lián)1個(gè)3-面,至多p?2個(gè)4-面或不關(guān)聯(lián)3-面,至多p個(gè)4-面,此時(shí)

p=3(?=8)時(shí),v會(huì)關(guān)聯(lián) 2個(gè)3-面,至多p?3個(gè)4-面或 1個(gè)3-面,至多p?2個(gè)4-面或不關(guān)聯(lián) 3-面,至多p個(gè)4-面.此時(shí)

如果n2(v)=6,由觀察(O3)和結(jié)構(gòu)性質(zhì)(b)(c),p=1(?=6)時(shí),v既不關(guān)聯(lián)3-面也不關(guān)聯(lián)4-面,此時(shí)

p=2(?=7)時(shí),v不關(guān)聯(lián) 3-面,至多 (p?1)個(gè) 4-面,此時(shí)

p=3(?=8)時(shí),v會(huì)關(guān)聯(lián)1個(gè) 3-面,至多(p?3)個(gè)4-面或不關(guān)聯(lián)3-面,至多 (p?1)個(gè)4-面,此時(shí)

特別地,?=7、8時(shí),情況如下:

如果n2(v)=7,由觀察(O3)和結(jié)構(gòu)性質(zhì)(b)(c),p=2(?=7)時(shí),v既不關(guān)聯(lián)3-面也不關(guān)聯(lián)4-面,此時(shí)

p=3(?=8)時(shí),v不關(guān)聯(lián)3-面,至多(p?2)個(gè)4-面.此時(shí)

如果n2(v)=8,p=3即?=8時(shí),v既不關(guān)聯(lián)3-面也不關(guān)聯(lián)4-面.此時(shí)

于是移值后,在任何一種情況下,對(duì)每個(gè)元素x∈V(G)∪F(G),有w′(x)≥0,所有點(diǎn)數(shù)值和這與矛盾,從而完成定理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.