唐保祥 , 任 韓

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

?

2類優(yōu)美圖的冠的優(yōu)美標(biāo)號(hào)*

唐保祥1, 任 韓2

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

優(yōu)美圖是圖論中重要的研究課題之一，有著廣泛的應(yīng)用價(jià)值和研究前景。但是目前仍然很難從理論上對(duì)一般圖的優(yōu)美性進(jìn)行研究。馬克杰猜想:所有優(yōu)美圖的冠都是優(yōu)美圖。這一猜想至今沒(méi)有被證明或否定。對(duì)任何正整數(shù)m和n,用構(gòu)造的方法給出了圖I(1-Fm,4)和I(K1,1,1,n)的優(yōu)美標(biāo)號(hào),從而證明了I(1-Fm,4)和I(K1,1,1,n)都是優(yōu)美圖。

優(yōu)美圖; 冠; 優(yōu)美標(biāo)號(hào)

圖的優(yōu)美標(biāo)號(hào)是目前圖論研究的一個(gè)熱點(diǎn)問(wèn)題[1-11],它的研究成果已經(jīng)應(yīng)用于密碼理論、天文學(xué)、導(dǎo)彈控制、雷達(dá)、通訊網(wǎng)絡(luò)尋址、數(shù)據(jù)庫(kù)管理等方面[1-2]。文獻(xiàn)[1]中給出了一個(gè)猜想：任意優(yōu)美圖的冠是優(yōu)美圖。這一猜想至今未被證明或否定。本文證明了兩類優(yōu)美圖的冠是優(yōu)美圖。

1 相關(guān)概念

定義1[1]圖G的每個(gè)頂點(diǎn)上都粘接r條懸掛邊(r≥1的整數(shù))得到的圖,叫做G的r-冠。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的一個(gè)優(yōu)美標(biāo)號(hào),θ′稱為由θ導(dǎo)出的邊標(biāo)號(hào)。

文獻(xiàn)[1]中把順序有一個(gè)公共頂點(diǎn)的m個(gè)4圈C4所形成的圖記為Fm,4(如圖1所示),Fm,4是優(yōu)美圖[1]。設(shè)V(Fm,4)={u0,u1,…,um,v1,v2,…,vn,w1,w2,…,wm},將頂點(diǎn)pi與圖Fm,4的頂點(diǎn)vi和wi分別連接一條邊(i=1,2,…,m)得到的圖記為1-Fm,4(如圖2所示)。

圖1 Fm,4圖Fig.1 Figure of Fm,4

圖2 1-Fm,4圖Fig.2 Figure of 1-Fm,4

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

定理1 ?m∈Z+,圖1-Fm,4是優(yōu)美圖。

例如, 圖1-F6,4的優(yōu)美標(biāo)號(hào)圖3所示。

圖3 圖1-F6,4的優(yōu)美標(biāo)號(hào)Fig.3 Graceful labeling of graph 1-F6,4

令S1={θ(ui)|i=0,1,…,m},S2={θ(pi)|i=1,2,…,m},

S3={θ(vi)|i=1,2,…,m},S4={θ(wi)|i=1,2,…,m}。

因?yàn)镾1∪S2={0,1,2,…,2m},minS3=2m+4,minS4=2m+1,max(S1∪S2)=2m-1, 所以Si∩Sj=?,i≠j。因此,映射θ:V(1-Fm,4)→{0,1,2,…,6m}是單射。

顯然θ(v1)-θ(u0),θ(v1)-θ(p1),θ(v1)-θ(u1),θ(w1)-θ(u0),θ(w1)-θ(p1),θ(w1)-θ(u1),θ(v2)-θ(u1),θ(v2)-θ(p2),θ(v2)-θ(u2),θ(w2)-θ(u1),θ(w2)-θ(p2),θ(w2)-θ(u2),…,θ(vm)-θ(um-1),θ(vm)-θ(pm),θ(vm)-θ(um),θ(wm)-θ(um-1),θ(wm)-θ(pm),θ(wm)-θ(um)是首項(xiàng)為6m,尾項(xiàng)是1,公差是1的等差數(shù)列,所以θ′:E(1-Fm,4)→{1,2,…,6m}是雙射,因此θ是圖1-Fm,4的一個(gè)優(yōu)美標(biāo)號(hào),圖1-Fm,4是優(yōu)美圖。證畢。

定理2 ?m∈Z+,圖1-Fm,4的冠I(1-Fm,4)是優(yōu)美圖。

證明 根據(jù)圖I(1-Fm,4)的定義,|V(I(1-Fm,4))|=8m+2,|E(1-Fm,4)|=10m+1。

設(shè)V(I(1-Fm,4))={u0,u1,…,um,v1,v2,…,vm,w1,w2,…,wm,p1,p2,…,pm,q1,q2,…,

qm,x1,x2,…,xm,y1,y2,…,ym,r0,r1,r2,…,rm},如圖4所示。

圖4 I(1-Fm,4)圖Fig.4 Figure of I(1-Fm,4)

定義圖I(1-Fm,4)頂點(diǎn)的標(biāo)號(hào)θ如下:

θ(ui)=6i,i=0,1,…,m;θ(pi)=2+6(i-1),i=1,…,m;

θ(vi)=10m-1-4(i-1),i=1,2,…m;θ(wi)=10m-4(i-1),i=1,2,…m;

θ(qi)=10m-6-4(i-1),i=1,2,…m;θ(xi)=3+6(i-1),i=1,…,m;

θ(yi)=5+6(i-1),i=1,…,m;θ(ri)=10m+1-4i,i=0,1,…,m

例如, 圖I(1-F6,4)的優(yōu)美標(biāo)號(hào)如圖5所示。

圖5 圖I(1-Fm,4)的優(yōu)美標(biāo)號(hào)Fig.5 Graceful labeling of graph I(1-Fm,4)

令S1={θ(ui)|i=0,1,…,m},S2={θ(pi)|i=1,2,…,m},S3={θ(vi)|i=1,2,…,m},S4={θ(wi)|i=1,2,…,m},S5={θ(qi)|i=1,2,…,m},S6={θ(xi)|i=1,2,…,m},S7={θ(yi)|i=1,2,…,m},S8={θ(ri)|i=0,1,2,…,m},則maxS1=6m, maxS2=6(m-1)+2, minS3=6m+3,minS4=6m+4,minS5=6m-2, maxS6=6m-3,maxS7=6m-1,minS8=6m+1,所以Si∩Sj=?,i≠j,i,j∈{1,2,…,8}。因此，映射θ:V(I(1-Fm,4))→{0,1,2,…,10m+1}是單射。

因?yàn)棣?ri-1)-θ(ui-1),θ(wi)-θ(ui-1),θ(vi)-θ(ui-1),θ(wi)-θ(pi),θ(vi)-θ(pi),θ(vi)-θ(xi),θ(wi)-θ(yi),θ(wi)-θ(ui),θ(vi)-θ(ui),θ(qi)-θ(pi)(i=1,2,…,m),θ(rm)-θ(um),是首項(xiàng)為10m+1,尾項(xiàng)是1,公差是1的等差數(shù)列, 故θ′:E(I(1-Fm,4))→{1,2,…,10m+1}是雙射,從而θ是圖I(1-Fm,4)的一個(gè)優(yōu)美標(biāo)號(hào),圖I(1-Fm,4)是優(yōu)美圖。證畢。

文獻(xiàn)[3]證明了：對(duì)任意正整數(shù)n，完全4部圖K1,1,1,n是優(yōu)美圖。例如, 圖K1,1,1,7的優(yōu)美標(biāo)號(hào)如圖6所示。

圖6 圖K1,1,1,7的優(yōu)美標(biāo)號(hào)Fig.6 Graceful labeling of the graph K1,1,1,7

定理3 ?n∈Z+,完全4部圖K1,1,1,n的冠I(K1,1,1,n)是優(yōu)美圖。

圖7 圖I(K1,1,1,n)Fig.7 Figure of I(K1,1,1,n)

定義圖I(K1,1,1,n)頂點(diǎn)的標(biāo)號(hào)θ如下:

θ(u0)=0;θ(u1)=n+1;θ(u3)=3n+6;

θ(x1)=n+2;θ(x2)=3n+5;θ(x3)=n+3;θ(vi)=3n+7+(i-1),i=1,2,…n;

θ(wi)=n+5+2(i-1),i=1,2,…n

例如, 圖I(K1,1,1,7)的優(yōu)美標(biāo)號(hào)圖8所示。

圖8 圖I(K1,1,1,7)的優(yōu)美標(biāo)號(hào)Fig.8 Graceful labeling of graph I(K1,1,1,7)

令S1={θ(vi)|i=0,1,…,n}∪{θ(x2),θ(u3)}={3n+5,3n+6,3n+7,…,4n+6},S2={θ(u1),θ(u2),θ(x1),θ(x3)}={0,n+1,n+2,n+3},S3={θ(wi)|i=1,2,…,n}={n+5,n+7,n+9,…,3n+3},則Si∩Sj=?,i≠j。因此,映射θ:V(I(1-Fm,4))→{0,1,2,…,10m+1}是單射。

因?yàn)棣?v1)-θ(u3),θ(v2)-θ(u3),…,θ(vn)-θ(u3),θ(u2)-θ(u1),θ(x1)-θ(u1),θ(vn)-θ(wn),θ(vn-1)-θ(wn-1),…,θ(v1)-θ(w1),θ(u3)-θ(x3),θ(x2)-θ(u2),θ(u3)-θ(u2),θ(vi)-θ(u2)(i=1,2,…,m),θ(u3)-θ(u1),θ(vi)-θ(u1)(i=1,2,…,m),是首項(xiàng)為1,尾項(xiàng)是4n+6,公差是1的等差數(shù)列, 故θ′:E(I(1-Fm,4))→{1,2,…,10m+1}是雙射,從而θ是圖I(K1,1,1,n)的一個(gè)優(yōu)美標(biāo)號(hào),圖I(K1,1,1,n)是優(yōu)美圖。證畢。

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

[2] ALON N. Combinarorics, probability and computing [M]. Cambridge: Cambridge University Press, 1999, 150-236.

[3] 唐保祥. 關(guān)于K1,2,n和K1,1,1,n的優(yōu)美性[J]. 上海師范大學(xué)學(xué)報(bào)：自然科學(xué)版, 1996, 24(4): 33-35.

[4] GALLIAN J A. A dynamic survey of graph labeling [J]. The Electronic Joumal of Combinatorics, 2013, 19, DS6:1-306.

[5] ZHOU X Q, YAO B, CHEN X E, et al. A proof to the odd-gracefulness of all lobsters [J]. Ars Combinatorial, 2012, 103: 13-18.

[6] KATHIESAN K M. Two classes of graceful graphs [J]. Ars Combinatorial, 2000, 22: 491-504.

[8] 孫宗劍，黎貞崇，羅海鵬，等. 升降梯圖L3m + n + 1的優(yōu)美性[J]. 計(jì)算機(jī)應(yīng)用研究, 2007, 24(12): 132-133.

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

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

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

Graceful Labeling of the Corona for Two Kinds of Graceful Graphs

TANGBaoxiang1,RENHan2

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

Graceful graph is one of the important research topics in graph theory with wide application and research prospects. But now it is still difficult to study the gracefulness of general graphs in theory. Ma Kejie conjecture is that all the coronas of graceful graph are graceful graphs. This conjecture has not been proved or denied. For any positive integersmandn, the constructor method gives graceful labeling ofI(1-Fm,4) andI(K1,1,1,n), thus prove thatI(1-Fm,4) andI(K1,1,1,n) are graceful graphs.

graceful graph; corona; graceful labeling

10.13471/j.cnki.acta.snus.2015.05.006

2015-01-24

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

唐保祥(1961年生)，男；研究方向：圖論和組合數(shù)學(xué);E-mail: tbx0618@sina.com

O157.5

A

0529-6579(2015)05-0024-04