带宽极图的一个反例

陆 锋

(湄洲湾职业技术学院 福建莆田 351254)

1 准备知识

笔者先给出一些本文将要用到的引理和定义.

引理1.4[3]当B=p-1时，Kp是e(p,B)的唯一极图.

定义1.1[4]对于任意整数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]定义图的联G=G1vG2v…vGk.设图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]设p=3k+r(1≤k,1≤r≤3)，则

图3 命题1的反例图

为了证明图3为命题2.1的反例.首先笔者证明如下命题：

命题：对于图3的图G，B(G)=5.

证明：如图4所示图G在该标号下B(G,f)=5.于是由带宽定义有B(G)≤5.

图4 B(G)≤5的带宽极图

假设f1为G的带宽为4的任一最优标号.首先考虑G的子图K3,1,1,1.显然在f1的标号下子图K3,1,1,1的带宽为4.而实际上，此时K3,1,1,1的非同构的标号顺序只有如图5显示的两种情况(因为若5度点标号为1或者6时，在此标号下的带宽值就为5.所以在带宽为4的最优标号下K3,1,1,1中任意5度点都不可能排在首或尾，且有对称性，3个5度点只有连续排列或者中间夹杂一个3度点.

图5 K3,1,1,1的非同构的标号顺序图

进一步笔者考虑点v.观察G易知，v与K3,1,1,1的3个3度点都相连.由于在图5的标号排列下首尾都是3度点，所以可见v无论插入该标号排列的哪个位置都将造成在此标号下G的带宽超过4，这与假设矛盾.所以假设不成立，于是B(G)，综上命题成立.证毕.

3 e(p,p-2)的所有极图

由e(p,B)和f(p,B)的定义可得e(p,B)≤f(p,B).笔者首先研究e(p,p-2)的极图的性质和结构.

下面定理给出e(p,p-2)的所有极图的构造公式.

定理3.2 设p=3k+r(1≤k,1≤r≤3)，则

证明：首先证(1).

(2)与(3)同理可得，证毕.图6列出e(7,5)极图的补图的所有情况.

图6 e(7,5)极图的补图

由定理3.1笔者有如下推论：

推论1[3]当B=p-2时，设p=3k+r(1≤k,1≤r≤3)，完全(k+1)-部图K3,3,…,3,r是e(p,B)的一个极图.

推论2设p=3k+r(1≤k,1≤r≤3)，则

(1)当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)的关系易知(2)(3)也成立.

参考文献：

[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].运筹学学报，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.