APP下载

带宽极图的一个反例

2013-12-03

九江学院学报(自然科学版) 2013年3期
关键词:易知反例标号

陆 锋

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

猜你喜欢

易知反例标号
序列(12+Q)(22+Q)…(n2+Q)中的完全平方数
几个存在反例的数学猜想
一个数论函数方程的可解性
从《曲律易知》看民国初年曲学理论的转型
活用反例扩大教学成果
一道高考立体几何题的多维度剖析
利用学具构造一道几何反例图形
基于路P8m+4t+2的交错标号的图S(4m+1,4(t+1),4m-1)的优美标号*
非连通图D3,4∪G的优美标号
非连通图(P1∨Pm)∪C4n∪P2的优美性