麥比烏斯梯子C(2n,n)的強邊色數

姚順禹,馬登舉

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

1 引言

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

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

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

2 主要結論

在本節的開始,先給出C(2n,n)的強邊色數的一個下界.

當n=2時,C(2n,n)即為K4,因為K4中任意兩條邊之間的距離都小于2,且K4含有6條邊,所以χ′s(C(4,2))=6.接下來,考慮n≥3的情形.

引理2.1當n≥3時,χ′s(C(2n,n))≥6.

證當n≥3時,C(2n,n)有一個導出子圖同構于如圖1所示的圖H.不難發現圖H中任何兩條邊之間的距離都不大于1.因圖H 含有6條邊,故(H)≥ 6,從而

圖1:圖H

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

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

由引理2.1知故只需證此時,只需給出C(2n,n)的一種只含有6種顏色的強邊染色.現定義C(2n,n)的一個邊染色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).不難驗證 f 符合強邊染色的定義,所以當n≡2(mod 4)時,χ′

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

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

只需證明當n2(mod 4)時,(C(2n,n))6.

當n≡ 0(mod 4)時,假設(C(2n,n))=6.此時,存在C(2n,n)的一個強邊染色f:E(G)→ {1,2,3,4,5,6}.首先邊v1v2,v1vn+1,v1v2n,v2v2+n,vn+1vn+2,vnvn+1中的任一條邊都需要染不同的顏色,因為在這些邊中任意兩條邊之間的距離都小于2.不妨設f(v1vn+1)=1,f(v1v2)=2,f(v1v2n)=3,f(vn+1vn+2)=4,f(vnvn+1)=5,f(v2vn+2)=6.因為v2v3與邊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.對剩下的邊染色,每一條邊只有一種顏色可染.染色規律如下

此時會發現,因為n≡0(mod 4),所以f(vn?1vn)=4,而f(vn+1vn+2)=4,但兩邊之間的距離為1,這與強邊染色的定義相矛盾,故當n≡0(mod 4)時同理,當n≡1或3(mod 4)時,

定理2.3當n/≡2(mod 4)時,

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

當n=4時,在C(8,4)中,圈D=v1v2v3···v8v1中任何兩條邊的距離都小于2.因圈D有8條邊,故對圈D強邊染色至少需要8種顏色.又因D中任何一邊與C(8,4)中除D以外的邊的距離都小于2,故染剩下的邊所用的顏色和圈D所用的顏色不同.在剩下的4條邊中,存在兩條邊之間的距離小于等于1,故剩下的4條邊至少需要兩種顏色.綜上所述,C(8,4)進行強邊染色至少需要10種顏色,即(C(8,4))≥10.現定義C(8,4)的一個邊染色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.不難驗證f是一個強邊染色,即(C(8,4))≤10,所以

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

綜上所述,任一種顏色在C(10,5)中所染的邊數不能大于等于3.因為C(10,5)共有15條邊,且(C(10,5))=7,所以至少存在一種顏色所染的邊數要大于等于3.故產生矛盾.故現定義C(10,5)的一個邊染色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.不難驗證邊染色g是一個強邊染色,即

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

綜上所述,任一顏色在C(16,8)中至多染四條邊.此時,設x為只染第二類邊的顏色數目.當x=0時,因為所以7種顏色至多染7×3=21條邊.當x=1時,至多染1×4+(7?1)×3=22條邊.當x=2時,至多染2×4+(7?2)×3=23條邊.當x≥3時,因為只有八條第二類邊,至多染8+(7?x)×3≤20條邊.而C(16,8)有24條邊,所以與假設矛盾.故(C(16,8))≥8,現定義C(16,8)的一個邊染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.不難驗證h是一個強邊染色,即(C(16,8))≤ 8.故 χ′s(C(16,8))=8.

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

圖2:當n=12時,(C(2n,n))=7

圖3:嵌入部分

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

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

圖4:當n=9時,(C(2n,n))=7

圖5:嵌入部分

圖6:當n=7時,(C(2n,n))=7

圖7:嵌入部分

參考文獻

[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.