唐保祥，任 韓

(1.天水師范學院數(shù)學與統(tǒng)計學院，甘肅 天水 741001； 2.華東師范大學數(shù)學系，上海 200062)

·研究簡報·

兩類圖及其冠的優(yōu)美標號

唐保祥1，任 韓2

(1.天水師范學院數(shù)學與統(tǒng)計學院，甘肅 天水 741001； 2.華東師范大學數(shù)學系，上海 200062)

用構(gòu)造法對兩類圖和兩類圖的冠的優(yōu)美性進行了研究，得到了如下結(jié)論：對任意正整數(shù)m和n，設(shè)Em和Pn分別是m個頂點的空圖和有n+1個頂點的路，那么完全3部圖K1，m，n，I(K1，m，2)，聯(lián)圖Em∨Pn和I(E2∨P2n)都是優(yōu)美圖.

路；聯(lián)圖；空圖；冠；優(yōu)美圖

1 預(yù)備知識

優(yōu)美圖的研究理論已有廣泛應(yīng)用，但是目前沒有系統(tǒng)理論對一般圖的優(yōu)美性進行研究.[1-12]馬克杰教授在文獻[1]中提出猜想：所有優(yōu)美圖的冠都是優(yōu)美圖.這一猜想至今沒有被證明或否定.若這個猜想正確，那么優(yōu)美圖的冠都是優(yōu)美圖，于是就有很多圖類被證明是優(yōu)美圖，這將是一個很有意義的結(jié)論.對任何正整數(shù)m和n，本文用構(gòu)造的方法給出了圖K1，m，n，I(K1，m，2)，聯(lián)圖Em∨Pn和I(E2∨P2n)的優(yōu)美標號，從而證明了這四類圖都是優(yōu)美圖.

定義1[1]圖G的每個頂點上都粘接1條懸掛邊得到的圖，稱為圖G的冠，記作I(G).

定義2[1]設(shè)圖G=(V，E).若存在單射θ：V(G)→{0，1，2，…，|E(G)|}，使得?e=uv∈E(G)，由θ′(e)=|θ(u)-θ(v)|導(dǎo)出雙射θ′：E(G)→{1，2，…，|E(G)|}，則稱圖G是優(yōu)美圖，θ稱為圖G的一個優(yōu)美標號，θ′稱為由θ導(dǎo)出的邊標號.

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

定理1 ?m，n∈Z+，完全3部圖K1，m，n是優(yōu)美圖.

證明顯然|E(K1，m，n)|=mn+m+n，|V(K1，m，n)|=m+n+1.設(shè)V(K1，m，n)={v1，v2，…，vm，w，u1，u2，…，un}.定義圖K1，m，n頂點的標號θ如下：

θ(vi)=mn+m+n+1-i，i=1，2，…，m；θ(w)=mn+n；θ(ui)=(m+1)(i-1)，i=1，2，…，n.

圖1 圖K1,5,4的優(yōu)美標號

例如，圖K1，5，4的優(yōu)美標號如圖1所示.

令S1={θ(vi)|i=1，2，…，m}∪{mn+n}，S2={θ(ui)|i=1，2，…，n}，則S1∪S2={0，m+1，2(m+1)，…，(n-1)(m+1)，mn+n，mn+n+1，…，mn+n+m}，S1∩S2=?.因此映射θ：V(K1，m，n)→{0，1，2，…，mn+m+n}是單射.

顯然θ(v1)-θ(u1)，θ(v2)-θ(u1)，…，θ(vm)-θ(u1)，θ(w)-θ(u1)，θ(v1)-θ(u2)，θ(v2)-θ(u2)，…，θ(vm)-θ(u2)，θ(w)-θ(u2)，…，θ(v1)-θ(un)，θ(v2)-θ(un)，…，θ(vm)-θ(un)，θ(w)-θ(un)，θ(v1)-θ(w)，θ(v2)-θ(w)，…，θ(vm)-θ(w)是首項為mn+m+n，尾項是1，公差是-1的等差數(shù)列，所以θ′：E(K1，m，n)→{1，2，…，mn+m+n}是雙射，故θ是圖K1，m，n的一個優(yōu)美標號，圖K1，m，n是優(yōu)美圖.

定理2 ?m∈Z+，圖K1，m，2的冠I(K1，m，2)是優(yōu)美圖.

證明根據(jù)定理1知圖K1，m，2是優(yōu)美圖.下面證明K1，m，2的冠I(K1，m，2)是優(yōu)美圖.由I(K1，m，2)的定義，|V(I(K1，m，2))|=2m+6，|E(I(K1，m，2))|=4m+5.

設(shè)V(I(K1，m，n))={v1，v2，…，vm，x1，x2，…，xm，w，z，u1，u2，y1，y2}.定義圖I(K1，m，n)頂點的標號θ如下：θ(vi)=4m+6-i，i=1，2，…，m；θ(xm+1-i)=3+2(i-1)，i=1，2，…，m；θ(w)=3m+5；θ(z)=1；θ(u1)=0；θ(u2)=2m+4；θ(y1)=2m+3；θ(y2)=2.

圖2 圖I(K1,5,2)的優(yōu)美標號

例如，圖I(K1，5，2)的優(yōu)美標號如圖2所示.

令S1={θ(vi)|i=1，2，…，m}∪{θ(w)}，S2={θ(xi)|i=1，2，…，m}∪{θ(z)，θ(y1)}，S3={θ(u1)，θ(u2)，θ(y2)}，則Si∩Sj=?(1≤i

因為θ(v1)-θ(u1)，θ(v2)-θ(u1)，…，θ(vm)-θ(u1)，θ(w)-θ(u1)，θ(w)-θ(z)，θ(vm)-θ(xm)，θ(vm-1)-θ(xm-1)，…，θ(v1)-θ(x1)，θ(y1)-θ(u1)，θ(y2)-θ(u2)，θ(v1)-θ(u2)，θ(v2)-θ(u2)，…，θ(vm)-θ(u2)，θ(w)-θ(u2)，θ(v1)-θ(w)，θ(v2)-θ(w)，…，θ(vm)-θ(w)是首項為4m+5，尾項是1，公差是-1的等差數(shù)列，故θ′：E(I(1-Fm，4))→{1，2，…，4m+5}是雙射，從而θ是圖I(K1，m，2)的一個優(yōu)美標號，圖I(K1，m，2)是優(yōu)美圖.

定理3 ?m，n∈Z+，m個頂點的空圖記為Em，長為n的路記為Pn，則聯(lián)圖Em∨Pn是優(yōu)美圖.

圖3 圖Em∨Pn

證明易知|V(Em∨Pn)|=m+n+1，|E(Em∨Pn)|=mn+m+n.設(shè)V(Em∨Pn)={u1，u2，…，v1，v2，…，vn+1}，如圖3所示.

下文中[x]表示不超過x的最大整數(shù).定義圖Em∨Pn頂點的標號θ如下：

θ(ui)=2n+1+(n+1)(i-1)，i=1，2，…，m；

令S1={θ(ui)|i=1，2，…，m}={2n+1，3n+2，4n+3，…，mn+m+n}，S2={θ(vi)|i=1，2，…，n+1}={0，1，2，…，n}，則S1∩S2=?.因此映射θ：V(Em∨Pn)→{0，1，2，…，mn+m+n}是單射.

注意到{θ(ui)-θ(vj)|i=1，2，…，m；j=1，2，…，n+n}∪{|θ(vj+1)-θ(vj)||j=1，2，…，n}={1，2，…，mn+m+n}，故θ′：E(Em∨Pn)→{1，2，…，mn+m+n}是雙射，從而θ是圖Em∨Pn的一個優(yōu)美標號，圖Em∨Pn是優(yōu)美圖.

定理4 ?n∈Z+，圖E2∨P2n的冠I(E2∨P2n)是優(yōu)美圖.

證明根據(jù)定理3知圖E2∨P2n是優(yōu)美圖.下面證明E2∨P2n的冠I(E2∨P2n)是優(yōu)美圖.由I(E2∨P2n)的定義知|V(I(E2∨P2n))|=4n+6，|E(I(E2∨P2n))|=8n+5.設(shè)V(I(E2∨P2n))={v1，v2，…，v2n+1，x1，x2，…，x2n+1，u1，u2，y1，y2}.定義圖I(E2∨P2n)頂點的標號θ如下：

θ(u1)=8n+5；θ(u2)=6n+4.

θ(x1)=4n+2；θ(x2)=2n+2.

令S1={θ(vi)|i=1，2，…，2n+1}，S2={θ(yi)|i=1，2，…，2n+1}，S3={θ(u1)，θ(u2)，θ(x1)，θ(x2)}，則S1={0，1，2，…，2n}，S2={2n+1，2n+3，2n+5，…，6n+1}，S3={8n+5，6n+4，4n+2，2n+2}，故Si∩Sj=?(1≤i

因為{θ(ui)-θ(vj)|i=1，2；j=1，2，…，2n+1}∪{θ(u1)-θ(x1)，θ(u2)-θ(x2)}∪{θ(vi)-θ(yi)|i=1，2，…，2n+1}∪{|θ(vi+1)-θ(vi)||i=1，2，…，2n}={1，2，…，8n+5}，故θ′：E(I(E2∨P2n))→{1，2，…，8n+5}是雙射，從而θ是圖I(E2∨P2n)的一個優(yōu)美標號，圖I(E2∨P2n)是優(yōu)美圖.

[1] 馬克杰.優(yōu)美圖[M].北京：北京大學出版社，1991：128-158.

[2] GALLIAN J A.A dynamic survey of graph labeling [J].The Electronic Journal of Combinatorics，2016，DS6：1-306.

[3] ALON N.Combinatorics，probability and computing [M].Cambridge：Cambridge University Press，1999：150-236.

[4] ZHOU XIANG-QIAN，YAO BING，CHEN XIANG-EN，et al.A proof to the odd-gracefulness of all lobsters [J].Ars Combinatorial，2012，103：13-18.

[5] KATHIESAN K M.Two classes of graceful graphs[J].Ars Combinatorial，2000，22：491-504.

[7] 唐保祥，任韓.2優(yōu)美圖的冠的優(yōu)美標號[J].中山大學大學報(自然科學版)，2015，54(5)：24-27.

[8] 容青，熊冬春.P2r，b圖的優(yōu)美性[J].系統(tǒng)科學與數(shù)學，2010，30(5)：703-709.

[9] 唐保祥，任韓.2類優(yōu)美圖[J].山東大學學報(理學版)，2010，45(10)：45-48.

[10] 唐保祥，任韓.3類特殊圖的優(yōu)美性[J].武漢大學學報(理學版)，2014，60(6)：553-556.

[11] 張志尚，黃文強.兩類并圖的優(yōu)美標號[J].東北師大學報(自然科學版)，2013，45(2)：30-34.

(責任編輯：李亞軍)

Thegracefullabelingoftwokindsgraphsanditscoronas

TANG Bao-xiang1，REN Han2

(1.School of Mathematics and Statistics，Tianshui Normal University，Tianshui 741001，China； 2.Department of Mathematics，East China Normal University，Shanghai 200062，China)

Constructive method for gracefulness of two kinds graphs and corona for two kinds of graphs was studied.The conclusions were obtained as：for arbitrary positive integern，m，Embe a empty graph withmvertices，Pnbe a path withn+1 vertices，the complete 3-partite graphsK1，m，n，I(K1，m，2)，a join graphEm∨PnandI(E2∨P2n) are graceful graphs.

path；join of two graphs；empty graph；corona；graceful graph

1000-1832(2017)03-0158-03

10.16163/j.cnki.22-1123/n.2017.03.031

2016-01-27

國家自然科學基金資助項目(11171114).

唐保祥(1961—)，男，教授，主要從事圖論和組合數(shù)學研究.

O 157.5 [學科代碼] 110·7470

A