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

王　濤, 魏　靜，李德明

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

?

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

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

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

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

關鍵詞:圖;優(yōu)美圖;k-強優(yōu)美圖

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

作者所討論的圖G(V,E)均為簡單無向圖,設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設圖G=(V,E),k為正整數(shù),如果存在一個單射f:V→{0,1,…,|E|+k-1},使得對所有的邊uv∈E,由f′(uv)=|f(u)-f(v)|導出一個雙射f′:E→{k,k+1,…,|E|+k-1},則稱圖G是k-優(yōu)美圖,f是G的一個k-優(yōu)美標號.1-優(yōu)美圖也稱優(yōu)美圖,1-優(yōu)美標號也稱優(yōu)美標號.

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

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

證明設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-強優(yōu)美標號

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

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

圖的優(yōu)美標號

圖的優(yōu)美標號

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

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

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

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

參考文獻：

[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]. 北京:北京大學出版社, 1991.

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

[4]梁志和.關于圖標號問題[J].河北師范大學學報 (自然科學版), 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]王 濤, 劉海生, 李德明. 和輪相關圖的優(yōu)美性 [J]. 中山大學學報 (自然科學版), 2011, 50 (6): 16-19.

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

(責任編輯朱夜明)

doi:10.3969/j.issn.1000-2162.2016.04.003

收稿日期：2015-05-06

基金項目:國家自然科學基金資助項目(10201022, 11101020);北京市自然科學基金資助項目(1102015);中央高校基本科研業(yè)務費資助項目(2011B019, JCB1207B, 3142014037);華北科技學院重點學科資助項目(HKXJZD201402)

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

中圖分類號：O157.5

文獻標志碼: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