陆 锋

(湄洲湾职业技术学院 福建莆田 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)，则

证明：……