帶寬極圖的一個反例

陸 鋒

(湄洲灣職業(yè)技術(shù)學(xué)院 福建莆田 351254)

1 準(zhǔn)備知識

筆者先給出一些本文將要用到的引理和定義.

引理1.4[3]當(dāng)B=p-1時，Kp是e(p,B)的唯一極圖.

定義1.1[4]對于任意整數(shù)k≥1，定義一個二部圖Hk=(X,Y;E)：其中頂點集為X∪Y，邊集為E，X={x1,x2,…,xk}，Y={y1,y2,…,yk}，E={xi,yj;i+j>k}.

例如：H1，H2，H3如圖1所示.

圖1 H1，H2，H3極圖

由引理1.5可知：

(1)B(G)=p-1成立的充要條件是G是完全圖；

定義1.2[5]若V(G1)∩v(G2)=?，定義G1和G2的并圖G1∪G2，其頂點集為V(G1)∪V(G2)，邊集為E(G1)∪E(G2).

定義1.3[5]定義圖的聯(lián)G=G1vG2v…vGk.設(shè)圖G1,G2,…,Gk個滿足如下條件：

(1)V1(G)∩V2(G)∩…∩Vk(G)=?；

(2)V(G)=V1(G)∪V2(G)∪…∪Vk(G)；

(3)E(G)={E(G1)∪E(G2)∪…∪E(Gk)∪{ui,vj};u∈V(Gi),v∈(Gj),1≤i≤k,1≤j≤k,i≠j}.

例如：p3vp4如圖2所示.

圖2 p3vp4極圖

2 反例

對于f(p,B)文章[1]給出如下命題：

命題2.1[1]設(shè)p=3k+r(1≤k,1≤r≤3)，則

圖3 命題1的反例圖

為了證明圖3為命題2.1的反例.首先筆者證明如下命題：

命題：對于圖3的圖G，B(G)=5.

證明：如圖4所示圖G在該標(biāo)號下B(G,f)=5.于是由帶寬定義有B(G)≤5.

圖4 B(G)≤5的帶寬極圖

假設(shè)f1為G的帶寬為4的任一最優(yōu)標(biāo)號.首先考慮G的子圖K3,1,1,1.顯然在f1的標(biāo)號下子圖K3,1,1,1的帶寬為4.而實際上，此時K3,1,1,1的非同構(gòu)的標(biāo)號順序只有如圖5顯示的兩種情況(因為若5度點標(biāo)號為1或者6時，在此標(biāo)號下的帶寬值就為5.所以在帶寬為4的最優(yōu)標(biāo)號下K3,1,1,1中任意5度點都不可能排在首或尾，且有對稱性，3個5度點只有連續(xù)排列或者中間夾雜一個3度點.

圖5 K3,1,1,1的非同構(gòu)的標(biāo)號順序圖

進(jìn)一步筆者考慮點v.觀察G易知，v與K3,1,1,1的3個3度點都相連.由于在圖5的標(biāo)號排列下首尾都是3度點，所以可見v無論插入該標(biāo)號排列的哪個位置都將造成在此標(biāo)號下G的帶寬超過4，這與假設(shè)矛盾.所以假設(shè)不成立，于是B(G)，綜上命題成立.證畢.

3 e(p,p-2)的所有極圖

由e(p,B)和f(p,B)的定義可得e(p,B)≤f(p,B).筆者首先研究e(p,p-2)的極圖的性質(zhì)和結(jié)構(gòu).

下面定理給出e(p,p-2)的所有極圖的構(gòu)造公式.

定理3.2 設(shè)p=3k+r(1≤k,1≤r≤3)，則

證明：首先證(1).

(2)與(3)同理可得，證畢.圖6列出e(7,5)極圖的補(bǔ)圖的所有情況.

圖6 e(7,5)極圖的補(bǔ)圖

由定理3.1筆者有如下推論：

推論1[3]當(dāng)B=p-2時，設(shè)p=3k+r(1≤k,1≤r≤3)，完全(k+1)-部圖K3,3,…,3,r是e(p,B)的一個極圖.

推論2設(shè)p=3k+r(1≤k,1≤r≤3)，則

(1)當(dāng)k=r=1時，f(p,p-2)=4，圖K2,2是f(p,p-2)的唯一極圖；

證明：由e(p,B)和f(p,B)的定義顯然可得e(p,B)≤f(p,B).若e(p,B)得一個極圖滿足△(G)≤B，則G也是f(p,B)的一個極圖.

由定理3.2以及e(p,B)和f(p,B)的關(guān)系易知(2)(3)也成立.

參考文獻(xiàn)：

[1]Yang Aifeng，Lin Yixun. Some results on an extreml bandwidth graph problem[J].Mathematica Applicata，2003，(16)1：143.

[2]DJ Miller. The Categorical product of graphs[J].Can J Math，1968，20(4)：1511.

[3]Ronald D Dutton, Robert C Brigham. On the size of graphs of a given bandwidth [J]. Discrete Mathematics，1989，76(3)：191.

[4]林治勛.圖帶寬問題的若干刻劃[J].運(yùn)籌學(xué)學(xué)報，2000，19(2):1.

[5]JA Bondy,USR Murty. Graph Theory[M]. Springer Verlag，2008.26.

[6]PZ Chinn，J Chvbtalovb， AK Dewdey，et al. The bandwidth problem for graphs and matrices-a survey [J]. Journal of Graph Theory，1982，6(3)：223.