麥比烏斯梯子C(2n,n)的強(qiáng)邊色數(shù)

姚順禹,馬登舉

(南通大學(xué)理學(xué)院,江蘇南通 226019)

1 引言

在圖G=(V(G),E(G))中,V(G),E(G)分別表示圖G的頂點(diǎn)集合,邊集合.圖G的一個(gè)k-邊正常染色是指一個(gè)映射f:E(G)→ {1,2,···,k},使得對(duì)于任何兩個(gè)相鄰的邊e1,e2,均有f(e1)f(e2),圖G的k-邊正常染色又簡(jiǎn)稱為k-邊染色.設(shè)G是一個(gè)圖,e1=u1v1,e2=u2v2是圖G中的兩條邊.若e1與e2相鄰,則稱e1與e2的距離為0,若e1與e2不相鄰,從e1的一個(gè)端點(diǎn)到e2的一個(gè)端點(diǎn)的路稱為e1到e2的一條路.e1與e2的距離是指在e1到e2的所有路中一條最短路所含的邊數(shù).圖G的k-強(qiáng)邊染色是一種k-正常染色,使得任意相鄰于同一條邊的兩條邊不得染相同的顏色.換句話說(shuō),圖G的強(qiáng)邊染色是一種邊染色,使得任意兩條距離不大于1的邊被染不同顏色.圖G的強(qiáng)邊色數(shù)(G)是最小的k,使得G有一個(gè)k-強(qiáng)邊染色.

1985年,Erd?s和Ne?etil[1]給出了關(guān)于強(qiáng)邊染色的概念,并提出了如下猜想:對(duì)于最大度為ΔG的圖G,Molloy和Reed[2]證明了當(dāng)ΔG足夠大時(shí),(G)≤這里 ∈約為.而Bruhn和Joos[3]進(jìn)一步證明了Andersen[4]證明了一個(gè)3-正則圖G的強(qiáng)邊色數(shù)

麥比烏斯梯子C(2n,n)是這樣一個(gè)圖,它的頂點(diǎn)集為V={vi|i=1,2,···,2n},邊集為E={vivi+1,vivi+n|i=1,2,···2n},這里的加法在取模2n的情況下進(jìn)行.它是一個(gè)3-正則圖,可以嵌入在射影平面上,當(dāng)n=3時(shí),C(2n,n)就是K3,3.本文研究了C(2n,n)的強(qiáng)邊色數(shù),得到如下結(jié)果:當(dāng)n=3時(shí),當(dāng)當(dāng)n=5,8時(shí)當(dāng)n≥3且n≡2(mod 4)時(shí),當(dāng)n≥7且n≡0,1或3(mod 4)時(shí),

2 主要結(jié)論

在本節(jié)的開始,先給出C(2n,n)的強(qiáng)邊色數(shù)的一個(gè)下界.

當(dāng)n=2時(shí),C(2n,n)即為K4,因?yàn)镵4中任意兩條邊之間的距離都小于2,且K4含有6條邊,所以χ′s(C(4,2))=6.接下來(lái),考慮n≥3的情形.

引理2.1當(dāng)n≥3時(shí),χ′s(C(2n,n))≥6.

證當(dāng)n≥3時(shí),C(2n,n)有一個(gè)導(dǎo)出子圖同構(gòu)于如圖1所示的圖H.不難發(fā)現(xiàn)圖H中任何兩條邊之間的距離都不大于1.因圖H 含有6條邊,故(H)≥ 6,從而

圖1:圖H

引理2.2當(dāng)n≥3時(shí),χ′s(C(2n,n))=6當(dāng)且僅當(dāng)n≡2(mod 4).

證 充分性設(shè)n≡2(mod 4),欲證χ′s(C(2n,n))=6.

由引理2.1知故只需證此時(shí),只需給出C(2n,n)的一種只含有6種顏色的強(qiáng)邊染色.現(xiàn)定義C(2n,n)的一個(gè)邊染色f:E(C(2n,n))→{1,2,3,4,5,6},如下:f(vivn+i)=1(i=1,3,5···,n?1);f(vivi+1)=2(i=1,5,9,···,2n?3);f(v1v2n)=f(vivi+1)=3(i=4,8,12,···,2n?4);f(vivi+1)=4(i=3,7,11,···,2n?1);f(vivi+1)=5(i=2,6,10,···,2n ? 2);f(vivn+i)=6(i=2,4,8,···,n).不難驗(yàn)證 f 符合強(qiáng)邊染色的定義,所以當(dāng)n≡2(mod 4)時(shí),χ′

s(C(2n,n))≤6.

必要性設(shè)(C(2n,n))=6,欲證n≡2(mod 4).

只需證明當(dāng)n2(mod 4)時(shí),(C(2n,n))6.

當(dāng)n≡ 0(mod 4)時(shí),假設(shè)(C(2n,n))=6.此時(shí),存在C(2n,n)的一個(gè)強(qiáng)邊染色f:E(G)→ {1,2,3,4,5,6}.首先邊v1v2,v1vn+1,v1v2n,v2v2+n,vn+1vn+2,vnvn+1中的任一條邊都需要染不同的顏色,因?yàn)樵谶@些邊中任意兩條邊之間的距離都小于2.不妨設(shè)f(v1vn+1)=1,f(v1v2)=2,f(v1v2n)=3,f(vn+1vn+2)=4,f(vnvn+1)=5,f(v2vn+2)=6.因?yàn)関2v3與邊v1v2,v1vn+1,v1v2n,v2v2+n,vn+1vn+2之間的距離都小于2,而與vnvn+1的距離等于2,所以f(v2v3)=5.同樣的,f(v1v2n)=f(vn+2vn+3)=3,f(v1vn+1)=f(v3vn+3)=1,f(vn+1vn+2)=f(v3v4)=4,f(vn+3vn+4)=f(v1v2)=2,f(v4vn+4)=f(v2vn+2)=6.對(duì)剩下的邊染色,每一條邊只有一種顏色可染.染色規(guī)律如下

此時(shí)會(huì)發(fā)現(xiàn),因?yàn)閚≡0(mod 4),所以f(vn?1vn)=4,而f(vn+1vn+2)=4,但兩邊之間的距離為1,這與強(qiáng)邊染色的定義相矛盾,故當(dāng)n≡0(mod 4)時(shí)同理,當(dāng)n≡1或3(mod 4)時(shí),

定理2.3當(dāng)n/≡2(mod 4)時(shí),

證當(dāng)n=3時(shí),在C(6,3)中,任兩條邊之間距離都小于2.所以一種顏色只能染一條邊,又C(6,3)有9條邊,所以(C(6,3))=9.

當(dāng)n=4時(shí),在C(8,4)中,圈D=v1v2v3···v8v1中任何兩條邊的距離都小于2.因圈D有8條邊,故對(duì)圈D強(qiáng)邊染色至少需要8種顏色.又因D中任何一邊與C(8,4)中除D以外的邊的距離都小于2,故染剩下的邊所用的顏色和圈D所用的顏色不同.在剩下的4條邊中,存在兩條邊之間的距離小于等于1,故剩下的4條邊至少需要兩種顏色.綜上所述,C(8,4)進(jìn)行強(qiáng)邊染色至少需要10種顏色,即(C(8,4))≥10.現(xiàn)定義C(8,4)的一個(gè)邊染色f:E(C(8,4)) → {1,2,···,10},如下:f(v1v2)=1,f(v2v3)=2,f(v3v4)=3,f(v4v5)=4,f(v5v6)=5,f(v6v7)=6,f(v7v8)=7,f(v8v1)=8,f(v1v5)=f(v3v7)=9,f(v2v6)=f(v4v8)=10.不難驗(yàn)證f是一個(gè)強(qiáng)邊染色,即(C(8,4))≤10,所以

當(dāng)n=5時(shí),由引理2.1與2.2知(C(10,5))≥7.現(xiàn)假設(shè)(C(10,5))=7.則存在一個(gè)強(qiáng)邊染色f:E(C(10,5))→{1,2,3,4,5,6,7}.為討論方便,稱圈A=v1v2v3···v10v1上的邊為第一類邊,其余的邊為第二類邊.因?yàn)槿上任意三條邊中,存在兩條邊使得它們之間的距離小于等于1,故當(dāng)一種顏色所染的邊都是第一類邊時(shí),這種顏色至多染兩條邊.因?yàn)榈诙愡叺娜我馊龡l邊中,存在兩條邊使得它們之間的距離小于等于1,故當(dāng)一種顏色所染的邊都是第二類邊時(shí),這種顏色至多染兩條邊.當(dāng)一種顏色所染的邊既有第一類邊又有第二類邊時(shí),不妨設(shè)所用的顏色為1,且v1v2被顏色1所染,即f(v1v2)=1,此時(shí)第二類邊中,只有v4v9可染與v1v2相同的顏色,那么顏色1至多可染兩條邊.

綜上所述,任一種顏色在C(10,5)中所染的邊數(shù)不能大于等于3.因?yàn)镃(10,5)共有15條邊,且(C(10,5))=7,所以至少存在一種顏色所染的邊數(shù)要大于等于3.故產(chǎn)生矛盾.故現(xiàn)定義C(10,5)的一個(gè)邊染色g:E(C(10,5))→{1,2,3,4,5,6,7,8},如下g(v1v6)=g(v4v9)=1,g(v1v2)=g(v8v9)=2,g(v1v10)=g(v7v8)=3,g(v6v7)=g(v3v4)=4,g(v5v6)=g(v3v8)=5,g(v2v7)=g(v5v10)=6,g(v4v5)=7,g(v2v3)=g(v9v10)=8.不難驗(yàn)證邊染色g是一個(gè)強(qiáng)邊染色,即

當(dāng)n=8時(shí),由引理2.1與2.2知現(xiàn)假設(shè)則存在一個(gè)強(qiáng)邊染色f:E(C(16,8))→ {1,2,3,4,5,6,7}.為討論方便,稱圈C=v1v2v3···v16v1上的邊為第一類邊,其余的邊為第二類邊.因?yàn)槿上任意四條邊中,存在兩條邊使得它們之間的距離小于等于1,故當(dāng)一種顏色所染的邊都是第一類邊時(shí),這種顏色至多染三條邊.因?yàn)榈诙愡叺娜我馕鍡l邊中,存在兩條邊使得它們之間的距離小于等于1,故當(dāng)一種顏色所染的邊都是第二類邊時(shí),這種顏色至多染四條邊.當(dāng)一種顏色所染的邊既有第一類邊又有第二類邊時(shí).不妨設(shè)所用的顏色為1,且v1v2被顏色1所染.即f(v1v2)=1.此時(shí)第二類邊中,f(v4v12),f(v5v13),f(v6v14),f(v7v15)可以等于1,當(dāng)f(v4v12)=1時(shí),剩下邊f(xié)(v6v7),可以等于1,但這五條邊中,任意兩邊之間的距離都小于2,故只有一條邊可染與v1v2相同的顏色,故顏色1至多染三條邊.故任一種顏色所染的邊既有第一類邊又有第二類邊時(shí),這種顏色至多能染三條邊.

綜上所述,任一顏色在C(16,8)中至多染四條邊.此時(shí),設(shè)x為只染第二類邊的顏色數(shù)目.當(dāng)x=0時(shí),因?yàn)樗?種顏色至多染7×3=21條邊.當(dāng)x=1時(shí),至多染1×4+(7?1)×3=22條邊.當(dāng)x=2時(shí),至多染2×4+(7?2)×3=23條邊.當(dāng)x≥3時(shí),因?yàn)橹挥邪藯l第二類邊,至多染8+(7?x)×3≤20條邊.而C(16,8)有24條邊,所以與假設(shè)矛盾.故(C(16,8))≥8,現(xiàn)定義C(16,8)的一個(gè)邊染1,h(v1v2)=h(v11v12)=h(v6v7)=2,h(v1v16)=h(v10v11)=h(v4v5)=3,h(v3v4)=h(v9v10)=h(v14v15)=4,h(v2v3)=h(v8v9)=h(v12v13)=5,h(v2v10)=h(v4v12)=h(v6v14)=h(v8v16)=6,h(v5v6)=h(v15v16)=7,h(v7v8)=h(v13v14)=8.不難驗(yàn)證h是一個(gè)強(qiáng)邊染色,即(C(16,8))≤ 8.故 χ′s(C(16,8))=8.

當(dāng)n≡0(mod 4)時(shí),由引理2.1與2.2知下面證(C(2n,n))≤7.為此先給出的一個(gè)有7種顏色的強(qiáng)邊染色,如圖2所示.而當(dāng)n＞12時(shí),只需將圖2中的邊v6v7與vn+6vn+7(n=4k,k≥3)刪除,并將點(diǎn)v6,vn+6,分別與圖3中的點(diǎn)a,b粘合,并分別將點(diǎn)v7,vn+7與c,d之間連一條邊,然后令f(c v7)=2,f(d vn+7)=4,即可得到C(2n,n)(n=4k,k＞3)的強(qiáng)邊色數(shù).

圖2:當(dāng)n=12時(shí),(C(2n,n))=7

圖3:嵌入部分

當(dāng)n≡1(mod 4)時(shí),由引理2.1與2.2知下面證明(C(2n,n))≤7,為此先給出C(18,9)的一個(gè)有7種顏色的強(qiáng)邊染色.如圖4所示.而當(dāng)n＞9時(shí),只需將圖4中的邊v7v8與vn+7vn+8(n=4k+1,k≥2)刪除,并將點(diǎn)v7,vn+7分別與圖5中的點(diǎn)a,b粘合,并分別將點(diǎn)v8,vn+8與c,d之間連一條邊,然后令f(c v8)=3,f(d vn+8)=5,即可得到C(2n,n)(n=4k+1,k＞2)的強(qiáng)邊色數(shù).

當(dāng)n≡3(mod 4)時(shí),由引理2.1與2.2知下面證明為此先給出C(14,7)的一個(gè)有7種顏色的強(qiáng)邊染色.如圖6所示.而當(dāng)n＞7時(shí),只需將圖6中的邊v6v7與vn+6vn+7(n=4k+3,k≥1)刪除,并將點(diǎn)v6,vn+6分別與圖7中的點(diǎn)a,b粘合,并分別將點(diǎn)v7,vn+7與c,d之間連一條邊,然后令f(c v7)=2,f(d vn+7)=4,即可得到C(2n,n)(n=4k+3,k＞1)的強(qiáng)邊色數(shù).

圖4:當(dāng)n=9時(shí),(C(2n,n))=7

圖5:嵌入部分

圖6:當(dāng)n=7時(shí),(C(2n,n))=7

圖7:嵌入部分

參考文獻(xiàn)

[1]Erd?s P.Problems and results in combinatorial analysis and graph theory[J].Ann.Disc.Math.,1988,38:81–92.

[2]Molloy M,Reed B.A bound on the strong chromatic index of a graph[J].J.Comb.The.,Ser.B,1997,69(2):103–109.

[3]Bruhn H,Joos F.A stronger bound for the strong chromatic index[J].Elec.Notes Disc.Math.,2015,49:277–284.

[4]Andersen L D.The strong chromatic index of a cubic graph is at most 10[J].Disc.Math.,1992,108(1-3):231–252.