兩類圖及其冠的優(yōu)美標(biāo)號(hào)

唐保祥，任 韓

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

·研究簡報(bào)·

兩類圖及其冠的優(yōu)美標(biāo)號(hào)

唐保祥1，任 韓2

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

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

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

1 預(yù)備知識(shí)

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

定義1[1]圖G的每個(gè)頂點(diǎn)上都粘接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的一個(gè)優(yōu)美標(biāo)號(hào)，θ′稱為由θ導(dǎo)出的邊標(biāo)號(hà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頂點(diǎn)的標(biāo)號(hào)θ如下：

θ(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)美標(biāo)號(hào)

例如，圖K1，5，4的優(yōu)美標(biāo)號(hào)如圖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)是首項(xiàng)為mn+m+n，尾項(xiàng)是1，公差是-1的等差數(shù)列，所以θ′：E(K1，m，n)→{1，2，…，mn+m+n}是雙射，故θ是圖K1，m，n的一個(gè)優(yōu)美標(biāo)號(hào)，圖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)頂點(diǎn)的標(biāo)號(hào)θ如下：θ(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)美標(biāo)號(hào)

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

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

因?yàn)棣?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)是首項(xiàng)為4m+5，尾項(xiàng)是1，公差是-1的等差數(shù)列，故θ′：E(I(1-Fm，4))→{1，2，…，4m+5}是雙射，從而θ是圖I(K1，m，2)的一個(gè)優(yōu)美標(biāo)號(hào)，圖I(K1，m，2)是優(yōu)美圖.

定理3 ?m，n∈Z+，m個(gè)頂點(diǎn)的空圖記為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頂點(diǎn)的標(biāo)號(hào)θ如下：

θ(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的一個(gè)優(yōu)美標(biāo)號(hào)，圖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)頂點(diǎn)的標(biāo)號(hào)θ如下：

θ(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

因?yàn)閧θ(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)的一個(gè)優(yōu)美標(biāo)號(hào)，圖I(E2∨P2n)是優(yōu)美圖.

[1] 馬克杰.優(yōu)美圖[M].北京：北京大學(xué)出版社，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)美標(biāo)號(hào)[J].中山大學(xué)大學(xué)報(bào)(自然科學(xué)版)，2015，54(5)：24-27.

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

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

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

[11] 張志尚，黃文強(qiáng).兩類并圖的優(yōu)美標(biāo)號(hào)[J].東北師大學(xué)報(bào)(自然科學(xué)版)，2013，45(2)：30-34.

(責(zé)任編輯：李亞軍)

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

國家自然科學(xué)基金資助項(xiàng)目(11171114).

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

O 157.5 [學(xué)科代碼] 110·7470

A