張志尚，張慶成，王春月

（1.吉林工程技術(shù)師范學(xué)院應(yīng)用理學(xué)院，吉林 長春 130052；

2.東北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，吉林 長春 130024）

關(guān)于（s〈c4，n〉）∪pm的優(yōu)美性

張志尚1，張慶成2，王春月1

（1.吉林工程技術(shù)師范學(xué)院應(yīng)用理學(xué)院，吉林 長春 130052；

2.東北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，吉林 長春 130024）

研究了（s〈c4，n〉）∪pm的優(yōu)美性，證明了：（1）m＝s－1時，（s〈c4，n〉）∪pm是優(yōu)美的；（2）s＝2t，m≥3＋s時，（s〈c4，n〉）∪pm是優(yōu)美的.其中：圖〈c4，n〉是將n個c4中的每一個c4的一個頂點粘接到一起得到的新圖，pm是m＋1個頂點的簡單路.（s〈c4，n〉）∪pm是s個〈c4，n〉與一個pm的不交并.

優(yōu)美標(biāo)號；優(yōu)美圖；不交并；路

1 預(yù)備知識

圖的優(yōu)美性研究起源于ROSA猜想，優(yōu)美性術(shù)語由S.W.Golomb給出［1］，目前已引起廣泛的關(guān)注和深入的研究，并在其他領(lǐng)域得到重要的應(yīng)用［2－3］.R.Frucht關(guān)于特殊的m與n得到了圖cn∪pm是優(yōu)美的結(jié)論［4］.董俊超證明了C4k∪C4k∪P4k＋t（1≤t≤3）具有優(yōu)美性［5］，張志尚等探討了C4k∪C4k∪Pm（m＝1或m≥n＋2）的優(yōu)美性［6］.本文研究了一類新的連通圖與路的并的優(yōu)美性.文中涉及未定義的圖論術(shù)語均與文獻(xiàn)［2］中的意義相同.

定義1對于一個圖G（V，E），如果對每一個v∈E，存在一個非負(fù)整數(shù)f（v）（稱為頂點v的標(biāo)號），使?jié)M足：（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為優(yōu)美圖，稱f為G的一個優(yōu)美值或優(yōu)美標(biāo)號.

定義2指定圖c4的一個頂點為根，將n個c4的根粘在一起得到的圖記為〈c4，n〉.粘結(jié)點記為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〉是優(yōu)美的，且〈c4，n〉的優(yōu)美標(biāo)號θ為：.引理2［7］?a∈｛0，1，…，m｝，路pm＝x0x1…xm存在一個優(yōu)美標(biāo)號g，使得g（x0）＝a.

2 主要結(jié)果及證明

圖1 圖（4〈c4，3〉）∪p9 及其優(yōu)美標(biāo)號

猜想 對?s≥2，?n，m，圖（s〈c4，n〉）∪pm是優(yōu)美的.

［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］ 馬克杰.優(yōu)美圖［M］.北京：北京大學(xué)出版社，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）的優(yōu)美性［J］.工程數(shù)學(xué)學(xué)報，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，F(xiàn)OURNIER I，GERMA A.Numotations gracieuses des chemins［J］.Ars Combin，1983，16：149-181.

［8］ 張志尚，王春月，張慶成.關(guān)于~ωn∪~ωn∪Pm的優(yōu)美性［J］.東北師大學(xué)報：自然科學(xué)版，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

國家自然科學(xué)基金資助項目（10871057）；吉林省教育廳“十一五”課題［吉教科合字（2007第227號）］.

張志尚（1962—），男，副教授，主要從事組合與圖論研究；通訊作者：張慶成（1960—），男，博士，副教授，主要從事李超代數(shù)，組合與圖論研究.

陶 理）