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

张志尚，张庆成，王春月

（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］.工程数学学报，2000，17（1）：133-134.

［6］ ZHANG ZHISHANG，WANG CHUNYUE.On the gracefulness of disjoint union graphC4n，C4nandPm［C］／／IEEE Computer Society，ICIECS2009United States，IEEE，2009，3：2185-2187.

［7］ FLANDRIN F，FOURNIER I，GERMA A.Numotations gracieuses des chemins［J］.Ars Combin，1983，16：149-181.

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

On the gracefulness of（s〈c4，n〉）∪pm

ZHANG Zhi-shang1，ZHANG Qing-cheng2，WANG Chun-yue1

（1.School of Applied Science，Jilin Teachers Institute of Engineering and Technology，Changchun 130052，China；
2.School of Mathematics and Statistics，Northeast Normal University，Changchun 130032，China）

The article does the research on the gracefulness of（s〈c4，n〉）∪pm，which proves that（s〈c4，n〉）∪pmis graceful in case thatm＝s－1，and the graph（s〈c4，n〉）∪pmis graceful in case thats＝2t，m≥3＋s，in which the graph〈c4，n〉is achieved by identifying a vertex of eachc4ofnc4s with one vertex；the graphpmis the path withm＋1vertexes，and the graph（s〈c4，n〉）∪pmis the disjoint union of s〈c4，n〉s andpm.

graceful label；graceful graph；disjoint union；path.

O 157.9

110·7470

A

1000-1832（2011）03-0014-05

2010-11-05

国家自然科学基金资助项目（10871057）；吉林省教育厅“十一五”课题［吉教科合字（2007第227号）］.

张志尚（1962—），男，副教授，主要从事组合与图论研究；通讯作者：张庆成（1960—），男，博士，副教授，主要从事李超代数，组合与图论研究.

陶 理）