唐保祥 , 任 韩
(1.天水师范学院数学与统计学院,甘肃 天水 741001;2.华东师范大学数学系,上海 200062)
2类优美图的冠的优美标号*
唐保祥1, 任 韩2
(1.天水师范学院数学与统计学院,甘肃 天水 741001;2.华东师范大学数学系,上海 200062)
优美图是图论中重要的研究课题之一,有着广泛的应用价值和研究前景。但是目前仍然很难从理论上对一般图的优美性进行研究。马克杰猜想:所有优美图的冠都是优美图。这一猜想至今没有被证明或否定。对任何正整数m和n,用构造的方法给出了图I(1-Fm,4)和I(K1,1,1,n)的优美标号,从而证明了I(1-Fm,4)和I(K1,1,1,n)都是优美图。
优美图; 冠; 优美标号
图的优美标号是目前图论研究的一个热点问题[1-11],它的研究成果已经应用于密码理论、天文学、导弹控制、雷达、通讯网络寻址、数据库管理等方面[1-2]。文献[1]中给出了一个猜想:任意优美图的冠是优美图。这一猜想至今未被证明或否定。本文证明了两类优美图的冠是优美图。
定义1[1]图G的每个顶点上都粘接r条悬挂边(r≥1的整数)得到的图,叫做G的r-冠。G的1-冠称为G的冠,记作I(G)。
定义2[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的一个优美标号,θ′称为由θ导出的边标号。
文献[1]中把顺序有一个公共顶点的m个4圈C4所形成的图记为Fm,4(如图1所示),Fm,4是优美图[1]。设V(Fm,4)={u0,u1,…,um,v1,v2,…,vn,w1,w2,…,wm},将顶点pi与图Fm,4的顶点vi和wi分别连接一条边(i=1,2,…,m)得到的图记为1-Fm,4(如图2所示)。

图1 Fm,4图Fig.1 Figure of Fm,4

图2 1-Fm,4图Fig.2 Figure of 1-Fm,4
定理1 ∀m∈Z+,图1-Fm,4是优美图。

例如, 图1-F6,4的优美标号图3所示。

图3 图1-F6,4的优美标号Fig.3 Graceful labeling of graph 1-F6,4
令S1={θ(ui)|i=0,1,…,m},S2={θ(pi)|i=1,2,…,m},
S3={θ(vi)|i=1,2,…,m},S4={θ(wi)|i=1,2,…,m}。
因为S1∪S2={0,1,2,…,2m},minS3=2m+4,minS4=2m+1,max(S1∪S2)=2m-1, 所以Si∩Sj=Ø,i≠j。因此,映射θ:V(1-Fm,4)→{0,1,2,…,6m}是单射。
显……