王　濤, 魏　靜，李德明

(1.華北科技學(xué)院 基礎(chǔ)部,河北 三河　065201； 2.首都師范大學(xué) 數(shù)學(xué)系,北京　100048)

?

幾類和扇有關(guān)圖的優(yōu)美性

王濤1, 魏靜1，李德明2

(1.華北科技學(xué)院 基礎(chǔ)部,河北 三河065201； 2.首都師范大學(xué) 數(shù)學(xué)系,北京100048)

摘要:證明下面的結(jié)論: 對任意自然數(shù)n≥2,圖是(n-1)-強(qiáng)優(yōu)美圖．對任意自然數(shù)∪G是優(yōu)美圖;對任意自然數(shù)n≥4,圖∪H是優(yōu)美圖, 其中.Pn是n個頂點的路, Gi為含有i條邊的優(yōu)美圖. 給定優(yōu)美圖Gn-1和其優(yōu)美標(biāo)號f, Gk-1和其優(yōu)美標(biāo)號g,設(shè)u∈Gn-1,v∈Gk-1且f(u)=g(v)=0, 取不同的兩邊xy和x′y′, 點x與u合并后得到的圖記為G, 點x′與v合并后得到的圖記為H.

關(guān)鍵詞:圖;優(yōu)美圖;k-強(qiáng)優(yōu)美圖

1972年,Golomb[1]給出了優(yōu)美圖的定義,隨后k-優(yōu)美圖、k-強(qiáng)優(yōu)美圖、協(xié)調(diào)圖、強(qiáng)協(xié)調(diào)圖等定義及圖標(biāo)號問題的進(jìn)展情況相繼給出[2-4].優(yōu)美標(biāo)號問題在編碼設(shè)計、通訊網(wǎng)絡(luò)、雷達(dá)脈沖等領(lǐng)域有重要應(yīng)用.近年來,人們?nèi)〉貌簧訇P(guān)于優(yōu)美性的結(jié)論[5-12].

作者所討論的圖G(V,E)均為簡單無向圖,設(shè)V=V(G)為圖G的頂點集,E=E(G)為圖G的邊集,|E|為圖G的邊數(shù),Kn是n個頂點的完全圖,Pn是n個頂點的路,St(n)為n+1個頂點的星.G1∨G2為圖G1與G2的聯(lián)圖,其頂點集合V(G1∨G2)=V(G1)∪V(G2),邊集合E(G1∨G2)=E(G1)∪E(G2)∪F,其中F={xy:x∈V(G1),y∈V(G2)}.聯(lián)圖K1∨Pm稱為扇,其中K1的頂點稱為扇的中心. [a]表示不超過實數(shù)a的最大整數(shù).

定義1設(shè)圖G=(V,E),k為正整數(shù),如果存在一個單射f:V→{0,1,…,|E|+k-1},使得對所有的邊uv∈E,由f′(uv)=|f(u)-f(v)|導(dǎo)出一個雙射f′:E→{k,k+1,…,|E|+k-1},則稱圖G是k-優(yōu)美圖,f是G的一個k-優(yōu)美標(biāo)號.1-優(yōu)美圖也稱優(yōu)美圖,1-優(yōu)美標(biāo)號也稱優(yōu)美標(biāo)號.

定義2設(shè)圖G=(V,E),k為正整數(shù),如果存在一個單射f:V→{0,k,…,|E|+k-1},使得對所有的邊uv∈E,由f′(uv)=|f(u)-f(v)|導(dǎo)出一個雙射f′:E→{k,k+1,…,|E|+k-1},則稱圖G是k-強(qiáng)優(yōu)美圖,f是G的一個k-強(qiáng)優(yōu)美標(biāo)號.

1K1∨(Pn∪Pn+1)的k-強(qiáng)優(yōu)美性

證明設(shè)K1:y0, Pn+1:x0,x1,x2,…,xn,Pn:xn+1,xn+2,…,x2n;|E|=4n.

f′(y0x0)=3n-1,f′(y0x1)=4n-2,

從而

的5-強(qiáng)優(yōu)美標(biāo)號

設(shè)g是圖Gn-1的一個優(yōu)美標(biāo)號,定義圖G的頂點標(biāo)號f為:當(dāng)v∈V(Gn-1)時,f(v)=g(v)+1.設(shè)增加的頂點為u,取f(u)=3n.

由于路Pn和星St(n-1)是(n-1)條邊的優(yōu)美圖,在優(yōu)美標(biāo)號為0的頂點增加懸掛邊,可以構(gòu)成Pn+1和St(n),因此,特殊的取G為Pn+1和St(n),可得文[11]中結(jié)論:

圖的優(yōu)美標(biāo)號

圖的優(yōu)美標(biāo)號

其中:a為數(shù)列1,2,…,n中的最大奇數(shù).

其中:b為數(shù)列1,2,…,n中的最大偶數(shù).

設(shè)g是圖Gk-1的一個優(yōu)美標(biāo)號,定義圖G的頂點標(biāo)號f為:當(dāng)v∈V(Gk-1)時,f(v)=g(v)+1.設(shè)增加的頂點為u,取f(u)=4n+k-1．

類似,由推論1、2可得推論3～4.

參考文獻(xiàn)：

[1]GOLOMB S W. How to number a graph, graph theory and computing[M]. New York: Academic Press, 1972: 23-37.

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

[3]康慶德. 圖標(biāo)號問題[J]. 河北師范學(xué)院學(xué)報 (自然科學(xué)版), 1991 (1): 102-115.

[4]梁志和.關(guān)于圖標(biāo)號問題[J].河北師范大學(xué)學(xué)報 (自然科學(xué)版), 2000, 24 (3): 300-303.

[5]CHENG H, YAO B, CHEN X, et al. On graceful generalized spiders and caterpillars[J]. Ars Combin, 2008, 87: 181-191.

[6]王 濤, 劉海生, 李德明. 和輪相關(guān)圖的優(yōu)美性 [J]. 中山大學(xué)學(xué)報 (自然科學(xué)版), 2011, 50 (6): 16-19.

[8]陳淑貞, 周俊梅. 關(guān)于聯(lián)圖P1∨Pn的k-強(qiáng)優(yōu)美性[J]. 數(shù)學(xué)雜志， 2010, 30 (2): 357-362.

(責(zé)任編輯朱夜明)

doi:10.3969/j.issn.1000-2162.2016.04.003

收稿日期：2015-05-06

基金項目:國家自然科學(xué)基金資助項目(10201022, 11101020);北京市自然科學(xué)基金資助項目(1102015);中央高?；究蒲袠I(yè)務(wù)費資助項目(2011B019, JCB1207B, 3142014037);華北科技學(xué)院重點學(xué)科資助項目(HKXJZD201402)

作者簡介：王濤(1972-)， 男, 河北遷安人, 華北科技學(xué)院副教授.

中圖分類號：O157.5

文獻(xiàn)標(biāo)志碼:A

文章編號:1000-2162(2016)04-0012-05

Gracefulness of some graphs related to Fan

WANG Tao1， WEI Jing1， LI Deming2

(1.Department of Foundation, North China Institute of Science and Technology, Sanhe 065201,China；(2.Department of Mathematics, Capital Normal University, Beijing 100048,China)

Abstract:This paper contained the following results: for any natural number n≥2, the graph was (n-1)-strong graceful; for any natural number n≥3, the graph ∪G was graceful; for any natural number n≥4, the graph ∪H was graceful, where ,Pn be a path with n vertices, and Gi be a graceful graph with i edges. Given a graceful graph Gn-1with its graceful labeling f, and Gk-1with its graceful labeling g,we assumed that a vertex u∈Gn-1, v∈Gk-1with f(u)=g(v)=0. Taking two copies of P2, xy and x′y′, identifying vertices x and u, x′ and v, we obtained the resulting graph G and H respectively.

Keywords:graph; graceful graph; k-strong graceful graph