2类优美图的冠的优美性证明*

唐保祥,任 韩

(1.天水师范学院数学与统计学院,甘肃 天水 741001;2.华东师范大学数学科学学院,上海 200062)

图的优美标号的研究成果已经应用于物流运输、晶体结构中原子位置的测定、X-射线密码技术、天文学、导弹控制、雷达、通讯网络寻址、数据库管理等方面[1-3].然而,至今还没有优美图的系统化研究方法,表征优美图的特征仍然是一个世界难题.目前,对优美图的证明是用构造性的方法给出一些特殊图类的优美标号,然后证明这些图是优美图[4-14].马克杰[1]曾给出一个猜想:任意优美图的冠是优美图.但这一猜想至今未被证明或否定.笔者拟证明优美图Tn和1-∧C4,n的冠I(Tn)和I(1-∧C4,n)都是优美图.

1 相关概念

定义1[1]设图G=(V,E),若存在单射θ:V(G)→{0,1,2,…,|E(G)|},使得∀e=uv∈E(G),由θ′(e)=|θ(u)-θ(v)|导出双射θ′:E(G)→{1,2,…,|E(G)|},则称图G是优美图, 称θ为图G的一个优美标号,称θ′为由θ导出的边标号.

定义2[1]图G的每个顶点上都粘接r条悬挂边(r≥1)得到的图,称为G的r-冠.G的1-冠称为G的冠,记作I(G).

将4圈ui1ui2ui3ui4ui1与ui+1,1ui+1,2ui+1,3ui+1,4ui+1,1的顶点ui2与ui+1,1(i=1,2,…,n-1)之间连接一条边，得到的图记作∧C4,n,如图1所示.

图1 图∧C4,n

将图∧C4,n的每个4圈的顶点ui1与ui3之间连接一条长为2的路ui1viui3(i=1,2,…,n)，得到的图记作1-∧C4,n,如图2所示.

图2 图1-∧C4,n

2条长为n的路为P1=u0u1…un,P2=v0v1…vn,分别连接路P1与P2的顶点ui与vi(i=0,1,…,n)，得到的图称为长为n的梯子,记作Tn,如图3所示.

图3 图Tn

为了研究方便,将梯子图画成与它同构的图，如图4所示.

图4 图Tn同构

2 主要结果及其证明

定理1对于∀n∈Z+,图1-∧C4,n和它的冠I(1-∧C4,n)都是优美图.

证明首先证明图1-∧C4,n是优美图.设图1-∧C4,n的顶点的集合为{ui1,ui2,ui3,ui4,vi|i=1,2,…,n},由图1-∧C4,n的定义易知,|E(1-C4,n)|=7n-1,|V(1-C4,n)|=5n.定义图1-∧C4,n的顶点的标号θ为

θ(ui4)=3(i-1),θ(vi)=3(i-1)+1,θ(ui2)=3(i-1)+2,

θ(ui1)=7n-1-4(i-1),θ(ui3)=7n-4-4(i-1)i=1,2,…,n.

例如,图1-∧C4,5的优美标号如图5所示.

图5 图1-∧C4,5的优美标号

按照标号θ的定义：图1-∧C4,n的顶点u14,v1,u12,u24,v2,u22,…,un4,vn,un3上的标号构成等差数列0,1,2,3,4,5,…,3(n-1),3(n-1)+1,3(n-1)+2,其通项为ai=i-1,i=1,2,…,n；图1-∧C4,n的顶点u11,u21,u31,…,un1上的标号构成等差数列7n-1,7n-5,7n-9,…,7n-1-4(n-1),其通项为bi=7n-1-4(i-1),i=1,2,…,n；图1-∧C4,n的顶点u13,u23,u33,…,un3上的标号构成等差数列7n-4,7n-7,7n-10,…,7n-4-4(n-1),其通项为ci=7n-4-4(i-1),i=1,2,…,n.

因为数列{ai}的最大项是3n-1,数列{bi}的最小项是3n+3,数列{ci}的最小项是3n+4,所以数列{ai}和{bi}没有公共项,数列{ai}和{ci}没有公共项,而数列{bi}和数列{ci}的对应项之差为3,从而数列{bi}和数列{ci}没有公共项.因此，映射θ:V(1-∧C4,n)→{0,1,2,…,|E(1-∧C4,n)|}是单射.

因为

{θ(ui1)-θ(ui4),θ(ui1)-θ(vi),θ(ui1)-θ(ui2),θ(ui3)-θ(ui4),θ(ui3)-θ(vi),

θ(ui3)-θ(ui2)}={7n-1-7(i-1),7n-2-7(i-1),7n-3-7(i-1),

7n-4-7(i-1),7n-5-7(i-1),7n-6-7(i-1)}i=1,2,…,n，

{θ(ui+1,1)-θ(ui2)}={7n-7-7(i-1)}i=1,2,…,n-1,

所以图1-∧C4,n由顶点标号导出的边标号的规律为：从左至右由4圈u11u22u33u44u11及连接该4圈的悬挂边再到4圈un1un2un3un4un1及连接该4圈的悬挂边上的边标号分别为7n-1,7n-2,7n-3,…,3,2,1.即由θ′(e)=|θ(u)-θ(v)|导出的映射θ′:E(1-∧C4,n)→{1,2,…,|E(1-∧C4,n)|}是双射.

于是θ是图1-∧C4,n的一个优美标号,图1-∧C4,n是优美图.

再证明图1-∧C4,n的冠I(1-∧C4,n)是优美图.设图I(1-∧C4,n)的顶点的集合为{ui1,ui2,ui3,ui4,vi,wi,xi1,xi2,yi1,yi2|i=1,2,…,n},如图6所示.由图I(1-∧C4,n)的定义易知,|E(I(1-C4,n))|=12n-1,|V(I(1-C4,n))|=10n.定义图I(1-∧C4,n)的顶点的标号θ为

图6 图I(1-∧C4,n)

θ(ui4)=6(i-1),θ(vi)=2+6(i-1),θ(ui2)=6(i-1)+4,

θ(xi1)=1+6(i-1),θ(yi2)=5+6(i-1),θ(yi1)=12n-1-6(i-1),

θ(xi2)=12n-4-6(i-1),θ(ui1)=12n-2-6(i-1),

θ(ui3)=12n-5-6(i-1),θ(w1)=12n-9-6(i-1)i=1,2,…,n.

例如,图I(1-∧C4,5)的优美标号如图7所示.

图7 图I(1-∧C4,5)的优美标号

令

S1={θ(xi1)|i=1,2,…,n}={1,7,13,…,1+6(n-1)},

S2={θ(xi2)|i=1,2,…,n}={12n-4,12n-10,12n-16,…,12n-4-6(n-1)},

S3={θ(ui4),θ(vi),θ(ui2)|i=1,2,…,n}={0,2,4,…,4+6(n-1)},

S4={θ(ui1)|i=1,2,…,n}={12n-2,12n-8,12n-14,…,12n-2-6(n-1)},

S5={θ(ui3)|i=1,2,…,n}={12n-5,12n-11,12n-17,…,12n-5-6(n-1)},

S6={θ(wi)|i=1,2,…,n}={12n-9,12n-15,12n-21,…,12n-9-6(n-1)},

S7={θ(yi1)|i=1,2,…,n}={12n-1,12n-7,12n-13,…,12n-1-6(n-1)},

S8={θ(yi2)|i=1,2,…,n}={5,11,17,…,6+6(n-1)}.

因为Sp∩Sq=Ø(p≠q,p,q∈{1,2,…,8}),所以映射θ:V(I(1-∧C4,n))→{0,1,2,…,|EI((1-∧C4,n))|}是单射.

因为

{θ(yi1)-θ(ui4),θ(ui1)-θ(ui4),θ(ui1)-θ(xi1),θ(ui1)-θ(vi),θ(ui3)-θ(ui4),

θ(ui1)-θ(ui2),θ(ui3)-θ(vi),θ(xi2)-θ(ui2),θ(ui3)-θ(ui2),

θ(ui3)-θ(yi2),θ(wi)-θ(vi)}={12n-1-12(i-1),

12n-2-12(i-1),12n-3-12(i-1),12n-4-12(i-1),

12n-5-12(i-1),12n-6-12(i-1),12n-7-12(i-1),

12n-8-12(i-1),12n-9-12(i-1),

12n-10-12(i-1),12n-11-12(i-1)}i=1,2,…,n,

{θ(ui+1,1)-θ(ui2)}={12n-12-12(i-1)}i=1,2,…,n-1,

所以图1-∧C4,n的冠I(1-∧C4,5)由顶点标号导出的边标号的规律为：从左至右由4圈u11u22u33u44u11及连接该4圈的悬挂边再到4圈un1un2un3un4un1及连接该4圈的悬挂边上的边标号分别为12n-1,12n-2,12n-3,…,3,2,1即由θ′(e)=|θ(u)-θ(v)|导出的映射θ′:EI((1-∧C4,n))→{1,2,…,|EI((1-∧C4,n))|}是双射.

于是θ是图I(1-∧C4,n)的一个优美标号,图I(1-∧C4,n)是优美图.

定理2对于∀n∈Z+,图Tn和它的冠I(Tn)是优美图.

证明先证图Tn是优美图.根据图Tn的定义,有|V(Tn)|=2n+2,|E(1-Fm,4)|=3n+1.设V(Tn)={u0,u1,…,un,v0,v1,…,vn},如图8所示，顶点标号显然是图Tn的一个优美标号,所以图Tn是优美图.

图8 图Tn的优美标号

再证I(Tn)是优美图.设图I(Tn)的顶点的集合为{xi,ui,vi,yi|i=1,2,…,n},如图9所示.由图I(Tn)的定义易知,|E(I(Tn))|=5n+3,|V(I(Tn))|=4n+4.定义图I(Tn)的顶点的标号θ为

图9 图I(Tn)

θ(xi)=1+3i,θ(ui)=5n+2-3i,θ(vi)=2i,θ(yi)=5n+3-3ii=0,1,2,…,n.

例如,图I(T8)的优美标号如图10所示.

图10 图I(T8)的优美标号

令

P1={θ(xi)|i=0,1,2,…,n}={1,3,5,…,1+3n},

P2={θ(ui)|i=0,1,2,…,n}={5n+2,5n-1,5n-4,…,2n+2},

P3={θ(vi)|i=0,1,2,…,n}={0,2,4,…,2n},

P4={θ(yi)|i=0,1,2,…,n}={5n+3,5n,5n-3,…,2n+3},

则Pi∩Pj=Ø,i≠j,i,j∈{0, 1,2,…,n}.因此,映射θ:V(I(Tn))→{0,1,2,…,4n+3}是单射.

因为

{θ(ui)-θ(xi),θ(ui)-θ(vi),θ(yi)-θ(vi)}={5n+1-5i,

5n+2-5i,5n+3-5i}i=0,1,2,…,n,

所以θ′:E(I(Tn))→{1,2,…,5n+3}是双射,从而θ是图I(Tn)的一个优美标号,图I(Tn)是优美图.