关于优美性的研究

张文慧，刘 萍，张 雪，张晓琢，张庆成

（东北师范大学数学与统计学院，吉林长春130024）

张文慧，刘 萍，张 雪，张晓琢，张庆成

（东北师范大学数学与统计学院，吉林长春130024）

研究了形如p（n1，n2，…，nm）∪p2n不交并图的优美性.证明了如果T.Gracl猜想成立，则形如p（n1，n2，…，nm）∪p2n不交并图的优美性在一定的条件下成立，并给出了当n＝3，4，5，6，7，8，9时，p（n1，n2，…，nm）∪p2n的优美标号.

优美标号；优美图；并图.

1 预备知识

图论中一个比较有趣的问题是所谓的图标号问题.图标号理论在射电天文学领域、组合设计和编码理论中有着广泛的应用［1－9］.

优美标号是图标号问题中首先提出的，其定义如下：

对于图G＝（V，E），如果对每一个v∈V，存在一个非负整数θ（v）（称为顶点v的标号）满足：

（ⅰ）∀u，v∈V，如果u≠v，那么θ（u）≠θ（v）.

（ⅱ）max｛θ（v）｜v∈V｝＝｜E｜.

（ⅲ）∀e1，e2∈E，如果e1≠e2，则θ′（e1）≠θ′（e2）.其中θ′（e）＝｜θ（u）－θ（v）｜，e＝uv.

则称G为优美图.称θ为G的一个优美值，或称优美标号.

1983年，T.Gracl提出猜想，设pn是n个点的路，则所有的都是优美图.这个猜想至今没有被证实或否定，所以研究形如p（n1，n2，…，nm）∪不交并图的优美性就有了意义.本文证明了，如果T.Gracl猜想成立，则形如p（n1，n2，…，nm）∪不交并图的优美性在一定的条件下成立，并给出了当n＝3，4，5，6，7，8，9时，p（n1，n2，…，nm）∪的优美标号.这一结论在一定意义下，对T.Gracl猜想的证明有所推动.

2 当n＝3～9时，优美猜想成立

具体例子见图1—7.

图1 p23的优美标号

图2 p24的优美标号

图3 p25的优美标号

图4 p26的优美标号

图5 p27的优美标号

图6 p28的优美标号

图7 p29的优美标号

3 主要结果

定理 若所有的p2n都是优美图，则对于任意自然数m，n和n1，n2，…，nm（m≥1，2≤n1≤n2≤…≤nm），若nm≥4n－4，则p（n1，n2，…，nm）∪pn2是优美图.

证明 Ⅰ 证明p（n1，n2，…，nm）中的点xi，j的标号各不相同.

（ⅰ）m＋nm为偶数.当i＋j为偶数时，标号从E逐渐减小，最小为θ（xm＋1，nm－1）；当i＋j为奇数时，标号从0逐渐增大，最大为θ（xm＋1，nm），且θ（xm＋1，nm－1）－θ（xm＋1，nm）＝2n－2.

（ⅱ）m＋nm为奇数.当i＋j为偶数时，标号从E逐渐减小，最小为θ（xm＋1，nm）；当i＋j为奇数时，标号从0逐渐增大，最大为θ（xm＋1，nm－1），且θ（xm＋1，nm）－θ（xm＋1，nm－1）＝2n－2.

综合以上两种情况可知：对于任意的i1，i2，j1，j2，当i1≠i2或j1≠j2时，θ（xi1，j1）≠θ（xi2，j2），即对于p（n1，n2，…，nm）中不同的点标号不同.

Ⅱ 由pn2的优美性知pn2中的点xi（i＝1，2，…，n）的标号各不同.

Ⅲ 证明pn2中点的标号与p（n1，n2，…，nm）中的各不相同.

因为

又

而

所以

又因为nm≥4n－4，且nm＝2k＋1，所以nm≥4n－3.因而θ（xm＋1，2）－θ（xm，nm）≥（－1）m·（4n－3），θ（xi）≠θ（xk，j），∀i，j，k∈Z.pn2中点的标号与p（n1，n2，…，nm）中的各不相同.

综上所述，p（n1，n2，…，nm）∪pn2中不同点的标号不同，且max ｛xi，j｝＝E，min ｛xi，j｝＝0.所以存在一个单射，使得V（G）→｛0，1，2，…，E｝，且E（G）↔｛1，2，…，E｝，是一个一一映射.因此p（n1，n2，…，nm）∪pn2是优美图.

推论 对于任意自然数m和n1，n2，…，nm（m≥1，2≤n1≤n2≤…≤nm），若nm≥4n－n，且n＝3，4，5，6，7，8，9，则p（n1，n2，…，nm）∪pn2是优美图.

证明 我们仅对n＝3，n＝9的情形进行证明，其他情形类似.

n＝3时的情形.

首先，证明p（n1，n2，…，nm）中的点xi，j的标号各不相同.

（1）m＋nm为偶数.当i＋j为偶数时，标号从E逐渐减小，最小为θ（xm＋1，nm－1）；当i＋j为奇数时，标号从0逐渐增大，最大为θ（xm＋1，nm），且θ（xm＋1，nm－1）－θ（xm＋1，nm）＝4.

（2）m＋nm为奇数.当i＋j为偶数时，标号从E逐渐减小，最小为θ（xm＋1，nm）；当i＋j为奇数时，标号从0逐渐增大，最大为θ（xm＋1，nm－1），且θ（xm＋1，nm）－θ（xm＋1，nm－1）＝4.

综合以上两种情况可知：对于任意的i1，i2，j1，j2，当i1≠i2或j1≠j2时，θ（xi1，j1）≠θ（xi2，j2）.即对于p（n1，n2，…，nm）中不同的点标号不同.

其次，证明p23中点xi（i＝1，2，3）的标号不同.由标号可知θ（x1）≠θ（x2）≠θ（x3）.

最后，证明p23中点的标号与p（n1，n2，…，nm）中的各不相同.

因为

且

所以

而nm≥8且nm＝2k＋1，所以nm≥9，θ（xm＋1，2）－θ（xm，nm）≥5·（－1）m.

θ（xi）≠θ（xk，j），∀i，j，k∈Z.所以p23中点的标号与p（n1，n2，…，nm）中的各不相同.

综上所述，p（n1，n2，…，nm）∪p23中不同点的标号不同，且max ｛xi，j｝＝E，min ｛xi，j｝＝0.所以存在一个单射，使得V（G）→｛0，1，2，…E｝，且E（G）↔｛1，2，…，E｝是一个一一映射.因此p（n1，n2，…，nm）∪p23是优美图.

给出p（n1，n2，…，nm）∪p23的优美标号：

先将p（n1，n2，…，nm）∪p23的顶点进行编号（见图8）.

图8 p（n1，n2，…，nm）∪p23的优美标号

图9 p（n1，n2，…，nm）∪p29的优美标号

（1）给x1，1和x1，2标号为.然后按以下公式给第一行的其他顶点标号为θ（x1，j）＝θ（x1，j－2）＋（－1）j（j＝3，4，…，n1）.

（2）设第i行已标号，对第i＋1行标号为：

（3）若p（n1，n2，…，nm）的各行顶点均已标号，上述算法停止，否则转入（2）.

（4）给p23中的xi（i＝1，2，3）进行如下标号：

n＝9时的情形（证明类似于n＝3时）.

给出p（n1，n2，…，nm）∪p29的优美标号：

先将p（n1，n2，…，nm）∪p29的顶点进行编号（见图9）.

（1）给x1，1和x1，2标号为.然后按公式给第一行的其他顶点标号.

（2）设第i行已标号，对第i＋1行标号为：

（3）若p（n1，n2，…，nm）的各行顶点均已标号，上述算法停止，否则转入（2）.

（4）给p29中的xi（i＝1，2，3）进行如下标号：

4 当n＝3～9时，p（n1，n2，…，nm）∪p2n的优美标号

具体情况见图10—16.

图10 p（2，3，4，9）∪p23的优美标号

图11 p（2，3，12）∪p24的优美标号

图12 p（2，3，4，9，12，16）∪p25的优美标号

图13 p（2，3，4，9，12，16，20）∪p26的优美标号

图14 p（2，3，4，9，12，16，20，25）∪p27的优美标号

图15 p（2，3，4，9，12，16，20，25，28）∪p28的优美标号.

图16 p（2，5，32）∪p29的优美标号

［1］ 马杰克.优美图［M］.北京：北京大学出版社，1991：65-121.

［2］ KOH K M，ROGERS D G，TAN T.A graceful arboretum：a survey of graceful trees［M］.Singapore Southeast Bull Math，1979：278-287.

［3］ HARARY F.Sum graphs and difference graphs［J］.Cong Number，1990，72：101-108.

［4］ 梁志和.关于图标号问题［J］.河北师范大学学报：自然科学版，2000，24（3）：300-303.

［5］ 杨燕吕，王广选.图pm∪pn的优美性初探［J］.北京工业大学学报，1993，19（4）：15-26.

［6］ 张志尚，王春月，张庆成.关于w～n∪w～n∪pm的优美性［J］.东北师大学报：自然科学版，2010，42（4）：30-34.

［7］ 马凤敏，吴晓春，张伟，等.关于n长路的（a，b；n）-优美标号［J］.东北师大学报：自然科学版，2012，44（4）：31-42.

［8］ 张志尚，黄文强.两类并图的优美性［J］.东北师大学报：自然科学版，2013，45（2）：30-34.

［9］ 吴跃生，王广富，徐保根.非连通图（P2∨¯Kn）（r1，r2，…，rn＋2）∪Gr的优美性［J］.东北师大学报：自然科学版，2014，46（3）：38-42.

On the gracefulness of graph p2n

ZHANG Wen-hui，LIU Ping，ZHANG Xue，ZHANG Xiao-zhuo，ZHANG Qing-cheng
（School of Mathematics and Statistics，Northeast Normal University，Changchun 130024，China）

A study has been done in this thesis on the gracefulness of a graph like disjoint union of p（n1，n2，…，nm）∪pn2.It is proved that the graph like disjoint union of p（n1，n2，…，nm）∪pn2is graceful under some condition if the hypothesis of T.Gracl is true.Moreover，we give the graceful labelings of p （n1，n2，…，nm）∪pn2when n＝3，4，5，6，7，8，9.In some sense，this work is also helpful for proving the hypothesis of T.Gracl.

graceful graph；graceful labeling；gear graph

O 157.5 ［学科代码］ 110·7470

A

（责任编辑：陶 理）

1000-1832（2015）03-0055-05

10.16163／j.cnki.22-1123／n.2015.03.012

2014-02-01

国家自然科学基金资助项目（61172094）；吉林省自然科学基金资助项目（20130101068）.

张文慧（1989—），女，硕士研究生，主要从事图论及李代数研究；通讯作者：张庆成（1960—），男，博士，教授，主要从事李代数、图论和组合设计研究.