2类优美图的冠的优美性证明*
时间：2023-02-28 17:15:04 来源：柠檬阅读网 本文已影响 人 
唐保祥,任 韩
(1.天水师范学院数学与统计学院,甘肃 天水 741001;2.华东师范大学数学科学学院,上海 200062)
图的优美标号的研究成果已经应用于物流运输、晶体结构中原子位置的测定、X-射线密码技术、天文学、导弹控制、雷达、通讯网络寻址、数据库管理等方面[1-3].然而,至今还没有优美图的系统化研究方法,表征优美图的特征仍然是一个世界难题.目前,对优美图的证明是用构造性的方法给出一些特殊图类的优美标号,然后证明这些图是优美图[4-14].马克杰[1]曾给出一个猜想:任意优美图的冠是优美图.但这一猜想至今未被证明或否定.笔者拟证明优美图Tn和1-∧C4,n的冠I(Tn)和I(1-∧C4,n)都是优美图.
定义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同构
定理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)是优美图.
猜你喜欢 易知标号通项 序列(12+Q)(22+Q)…(n2+Q)中的完全平方数聊城大学学报（自然科学版）(2022年2期)2022-11-19数列通项与求和新高考·高三数学(2022年3期)2022-04-28一个数论函数方程的可解性山西大同大学学报(自然科学版)(2021年3期)2021-06-24n分奇偶时，如何求数列的通项中学生数理化(高中版.高二数学)(2020年9期)2020-10-27巧求等差数列的通项中学生数理化(高中版.高二数学)(2020年9期)2020-10-27求数列通项课教学实录及思考河北理科教学研究(2020年1期)2020-07-24从《曲律易知》看民国初年曲学理论的转型戏曲研究(2017年3期)2018-01-23一道高考立体几何题的多维度剖析数学学习与研究(2017年14期)2017-07-20钢材分类标号（一）新疆钢铁(2016年3期)2016-02-28基于路P8m+4t+2的交错标号的图S(4m+1,4(t+1),4m-1)的优美标号*中山大学学报(自然科学版)(中英文)(2015年5期)2015-06-08
