张志尚，张庆成，王春月

（1.吉林工程技术师范学院应用理学院，吉林 长春 130052；

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

关于（s〈c4，n〉）∪pm的优美性

张志尚1，张庆成2，王春月1

（1.吉林工程技术师范学院应用理学院，吉林 长春 130052；

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

研究了（s〈c4，n〉）∪pm的优美性，证明了：（1）m＝s－1时，（s〈c4，n〉）∪pm是优美的；（2）s＝2t，m≥3＋s时，（s〈c4，n〉）∪pm是优美的.其中：图〈c4，n〉是将n个c4中的每一个c4的一个顶点粘接到一起得到的新图，pm是m＋1个顶点的简单路.（s〈c4，n〉）∪pm是s个〈c4，n〉与一个pm的不交并.

优美标号；优美图；不交并；路

1 预备知识

图的优美性研究起源于ROSA猜想，优美性术语由S.W.Golomb给出［1］，目前已引起广泛的关注和深入的研究，并在其他领域得到重要的应用［2－3］.R.Frucht关于特殊的m与n得到了图cn∪pm是优美的结论［4］.董俊超证明了C4k∪C4k∪P4k＋t（1≤t≤3）具有优美性［5］，张志尚等探讨了C4k∪C4k∪Pm（m＝1或m≥n＋2）的优美性［6］.本文研究了一类新的连通图与路的并的优美性.文中涉及未定义的图论术语均与文献［2］中的意义相同.

定义1对于一个图G（V，E），如果对每一个v∈E，存在一个非负整数f（v）（称为顶点v的标号），使满足：（1）max｛f（v）｜v∈V｝＝｜E（G）｜；（2）∀u，v∈E，如果u≠v，则f（u）≠f（v）；（3）∀e1，e2∈E（G），如果e1≠e2，则f′（e1）≠f′（e2）.其中f′（e）＝｜f（u）－f（v）｜，uv＝e.则称G为优美图，称f为G的一个优美值或优美标号.

定义2指定图c4的一个顶点为根，将n个c4的根粘在一起得到的图记为〈c4，n〉.粘结点记为b.〈c4，n〉中的每个c4称为分支，相继顶点记为：b，ui，vi，wi（i＝1，2，…，n）.pm是m＋1个顶点的简单通路.图（s〈c4，n〉）∪pm是s个〈c4，n〉与一个pm的不交并.

引理1［3］图〈c4，n〉是优美的，且〈c4，n〉的优美标号θ为：.引理2［7］∀a∈｛0，1，…，m｝，路pm＝x0x1…xm存在一个优美标号g，使得g（x0）＝a.

2 主要结果及证明

图1 图（4〈c4，3〉）∪p9 及其优美标号

猜想 对∀s≥2，∀n，m，图（s〈c4，n〉）∪pm是优美的.

［1］ GOLOMB S W.How to number a graph［C］／／READ R C，ed.In Graph Theory and Computing，New York：Academic Press，1972：23-37.

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

［3］ GALLIAN J A.A dynamic survey of graph labeling［J／OL］.［2009-03-20］.http：∥www.combinatorics.org／Surveys.

［4］ FRUCHT R，SALINAS L C.Graceful numbering of snakes with constraints on therst label［J］.Ars Combin，1985，20（B）：143-157.

［5］ 董俊超.C4k∪C4k∪P4k＋t（1≤t≤3）的优美性［J］.工程……