2类优美图的冠的优美标号*

2015-06-08 02:49:27唐保祥
关键词:定义

唐保祥 , 任 韩

(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[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

2 主要结果及其证明

定理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}是单射。

显……

登录APP查看全文

猜你喜欢
定义
活用定义巧解统计概率解答题
例谈椭圆的定义及其应用
题在书外 根在书中——圆锥曲线第三定义在教材和高考中的渗透
永远不要用“起点”定义自己
海峡姐妹(2020年9期)2021-01-04 01:35:44
严昊:不定义终点 一直在路上
华人时刊(2020年13期)2020-09-25 08:21:32
定义“风格”
成功的定义
山东青年(2016年1期)2016-02-28 14:25:25
有壹手——重新定义快修连锁
修辞学的重大定义
当代修辞学(2014年3期)2014-01-21 02:30:44
山的定义
公务员文萃(2013年5期)2013-03-11 16:08:37