王濤，王清，李德明

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

圖的優(yōu)美標(biāo)號問題起源于20世紀(jì)60年代，自它問世以來，一直是組合數(shù)學(xué)的一個熱門課題，它在數(shù)學(xué)理論及實際應(yīng)用領(lǐng)域都有其重要的研究價值，如運用優(yōu)美標(biāo)號來解決完全圖分解為同構(gòu)子圖的問題，糾錯碼設(shè)計、通訊網(wǎng)絡(luò)、雷達(dá)脈沖、導(dǎo)彈控制碼設(shè)計等等［1］。在圖的優(yōu)美性的研究成果中，多數(shù)是關(guān)于連通圖優(yōu)美性的研究［2－7］，近年來，人們開始關(guān)注非連通圖優(yōu)美性問題，并取得不少關(guān)于此條件下的優(yōu)美性的結(jié)論［8－12］。

以下所討論的圖G(V，E)均為簡單無向圖，設(shè)V=V(G)為圖G的頂點集，E=E(G)為圖G的邊集。為集合A的階數(shù)，Cn是長度為n的圈，Pn

1 A～B優(yōu)美圖

2 非連通圖(C3∨∪G及(P3∨)∪G的優(yōu)美性

圖1 (P3∨∪3，4)的優(yōu)美標(biāo)號Fig.1 The graceful labeling of??K(P3∨)∪3，4)

特殊地，推論1中，取k=1，即得文［8］的結(jié)論:對任意正整數(shù)m，n，t，滿足min{n，t}≤m，非連通圖是優(yōu)美圖。

推論2對任意正整數(shù)m，n，t，如果2≤n＜2m+1，則

P(j)圖2(C3∨10的優(yōu)美標(biāo)號Fig.2 The graceful labeling of(C3∨)

推論3對任意正整數(shù)m，n，t，如果2≤n≤2m+1，則圖(C3∨∪Pn∪St(t)是優(yōu)美圖。

圖3 (C3∨∪P9∪St(6)的優(yōu)美標(biāo)號Fig.3 The graceful labeling of(C3∨∪P9∪St(6)

特殊地，推論3中，取n=2，即得文［9］的結(jié)論:對任意正整數(shù)m，有(C3∨∪St(t)∪K2是優(yōu)美圖。

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

［2］ CHENG H，YAO B，CHEN X，et al.On graceful generalized spiders and caterpillars［J］.Ars Combin，2008，87:181－191.

［3］ YANG Y S，RONG Q，XU X R.A class of graceful graphs［J］.Math Research and Exposition，2004，24:520－524.

［4］ YANG Y，XU X，XI Y，et al.The graphsre graceful for t≡0，1(mod 4)［J］.Ars Combin，2006，79:295－301.

［5］ YANG Y，XU X，XI Y，et al.The graphsre graceful for t≡0，3(mod 4)［J］.Ars Combin，2007，85:361－368.

［6］ YOUSSEF M Z.On Skolem－graceful and cordial graphs［J］.Ars Combin，2006，78:167－177.

［7］ 劉家保，潘向峰.輪形圖和扇型圖的優(yōu)美性［J］.安徽大學(xué)學(xué)報:自然科學(xué)版，2009，33(4):11－13.

［8］ 劉瑞芹，張昆龍.非連通并圖的優(yōu)美標(biāo)號研究［J］.合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2009，32(6):940－944.

［9］ 魏麗俠，賈治中.非連通圖G1∪G2及G1∪G2∪K2的優(yōu)美性［J］.應(yīng)用數(shù)學(xué)學(xué)報，2005，28(4):689－694.

［10］ 蔡華，魏麗俠，呂顯瑞.非連通圖(P1∨Pn)∪Gr和(P1∨Pn)∪(P3∨及Wn∪St(m)的優(yōu)美性［J］.吉林大學(xué)學(xué)報:理學(xué)版，2007，7(4):540－543.

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

［12］ 潘偉，路線.兩類非連通圖(P2∨∪St(m)及(P2∨)∪Tn的優(yōu)美性［J］.吉林大學(xué)學(xué)報:理學(xué)版，2003，41(2):152－154.