非連通圖G+e∪Hk-1的優(yōu)美性*

吳躍生

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西 南昌330013)

非連通圖G+e∪Hk-1的優(yōu)美性*

吳躍生

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西 南昌330013)

證明了當(dāng)k≥2時(shí)，非連通圖G+e∪Hk-1是優(yōu)美圖,其中G是特征為k的平衡二分圖，Hk-1是任意一個(gè)k-1條邊的優(yōu)美圖.

優(yōu)美圖;非連通圖；平衡二分圖

1 相關(guān)定義

文中所討論的圖均為無向簡(jiǎn)單圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集.為了簡(jiǎn)單起見，將一個(gè)有p個(gè)頂點(diǎn)q條邊的圖記為(p,q)-圖.記號(hào)[m,n]表示整數(shù)集合{m，m+1,m+2,...，n}，其中m和n均為非負(fù)整數(shù)，且滿足0≤m

圖的優(yōu)美標(biāo)號(hào)問題是組合數(shù)學(xué)中一個(gè)熱門課題[1-11].

定義1[1]對(duì)于一個(gè)圖G=(V,E)，若存在一個(gè)單射θ:V(G)→[0,|E(G)|]使得對(duì)所有邊e=(u,v)∈E(G)，由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的E(G)→[1,|E(G)|]是一個(gè)雙射，則稱G是優(yōu)美圖.θ是G的一組優(yōu)美標(biāo)號(hào)，稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值.

定義2[1]設(shè)f為G的一個(gè)優(yōu)美標(biāo)號(hào)，若存在一個(gè)正整數(shù)k，使得對(duì)任意的uv∈E(G)，有f(u)>k≥f(v)或f(u)≤k

顯然，若f為G的平衡標(biāo)號(hào)，則k是邊導(dǎo)出標(biāo)號(hào)為1的邊的2個(gè)端點(diǎn)中標(biāo)號(hào)較小的頂點(diǎn)的標(biāo)號(hào).

定義3[1]在平衡二分圖G中，設(shè)其優(yōu)美標(biāo)號(hào)θ的特征為k，并且θ(u0)=k，θ(v0)=k+1，則稱u0為G的二分點(diǎn)，v0為G的對(duì)偶二分點(diǎn).

定義5[1]v1,v2是圖G的2個(gè)非鄰接的頂點(diǎn)，則e=v1v2?E(G).用G+e表示頂點(diǎn)集為V(G)，且邊集為E(G)∪{e}的圖，即V(G+e)=V(G),E(G+e)=E(G)∪{e}.

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

再令θ3(v)=q-θ2(v),v∈V(G),則θ,θ1,θ2,θ3是圖G的互不相同的4種平衡標(biāo)號(hào),其特征分別為k,q-k-1,k和q-k-1.

定理1 當(dāng)k≥2時(shí)，(p,q)-圖G是特征為k的平衡二分圖，Hk-1是邊數(shù)為k-1的優(yōu)美圖，則非連通圖G+e∪Hk-1是優(yōu)美的.

證明設(shè)V(G)劃分成2個(gè)集合X,Y,θ是圖G的平衡標(biāo)號(hào),且：(1)v1,v2∈X,θ(v1)=0,θ(v2)=k,即v2是平衡二分圖G的二分點(diǎn)；(2)存在v1,v2∈Y，有|θ(v1)-θ(v2)|=k.

定義圖G+e∪Hk-1的頂點(diǎn)標(biāo)號(hào)θ1為

下面證明標(biāo)號(hào)θ1是圖G+e∪Hk-1的優(yōu)美標(biāo)號(hào).

因此θ1是圖G+e∪Hk-1的優(yōu)美標(biāo)號(hào).證畢.

由引理1和定理1有如下結(jié)論：

推論1 當(dāng)q-k-2≥時(shí)，(p,q)-圖G是特征為k的平衡二分圖，Hq-k-2是邊數(shù)為q-k-2的優(yōu)美圖，則非連通圖G+e∪Hq-k-2是優(yōu)美的.

證明設(shè)(p,q)-圖G的關(guān)于平衡標(biāo)號(hào)θ的特征為k,θ(v1)=q，θ(v2)=k+1，令θ1(v)=q-θ(v),v∈V(G).由引理1知，θ1是(p,q)-圖G的另一個(gè)平衡標(biāo)號(hào)，(p,q)-圖G的關(guān)于平衡標(biāo)號(hào)θ的特征為q-k-1，且有θ1(v1)=0，θ1(v2)=q-k-1.由定理1知，非連通圖G(v1v2)∪Hq-k-2是優(yōu)美的.證畢.

在定理1中，令Hk-1=St(k-1)(St(k-1)表示有k個(gè)頂點(diǎn)或有k-1條邊的星形樹)，有如下結(jié)論：

推論2 當(dāng)k≥2,(p,q)-圖G是特征為k的平衡二分圖時(shí)，G+e∪St(k-1)是優(yōu)美圖.

在定理1中，令Hk-1=Pk(Pk表示有k個(gè)頂點(diǎn)或有k-1條邊的路)，有如下結(jié)論：

推論3 當(dāng)k≥2,(p,q)-圖G是特征為k的平衡二分圖時(shí),G+e∪Pk是優(yōu)美圖.

在定理1中，令Hk-1=Tk(Tk表示有k個(gè)頂點(diǎn)或有k-1條邊的優(yōu)美樹)，有如下結(jié)論：

推論4 當(dāng)k≥2,(p,q)-圖G是特征為k的平衡二分圖時(shí),G+e∪Tk是優(yōu)美圖.

在定理1中，令Hk-1=Ck-1,k=4n,有如下結(jié)論：

推論5 當(dāng)n≥1,(p,q)-圖G是特征為4n的平衡二分圖時(shí)，G+e∪C4n-1是優(yōu)美圖.

在定理1中，令Hk-1=Ck-1,k=4n+1,有如下結(jié)論：

推論6 當(dāng)n≥1,(p,q)-圖G是特征為4n+1的平衡二分圖時(shí),G+e∪C4n是優(yōu)美圖.

在定理1中，令Hk-1=Ck-2⊙K1,當(dāng)k≥5時(shí),Ck-2⊙K1是優(yōu)美圖，所以有如下結(jié)論：

圖1 C9∪St(3)的優(yōu)美標(biāo)號(hào)

推論7 當(dāng)k≥5,(p,q)-圖G是特征為k的平衡二分圖時(shí),G+e∪Ck-2⊙K1是優(yōu)美圖.

例1 根據(jù)定理1和推論給出的P9+e∪St(3)的優(yōu)美標(biāo)號(hào)(而此時(shí)P9+e=C9)如圖1所示,C8+e∪P4的優(yōu)美標(biāo)號(hào)如圖2所示，C8+e∪P3的優(yōu)美標(biāo)號(hào)如圖3—5所示,K2,5+e∪C3的優(yōu)美標(biāo)號(hào)如圖6所示，K2,5+e∪C4的優(yōu)美標(biāo)號(hào)如圖7所示.

圖2 C8+e∪P4的優(yōu)美標(biāo)號(hào)

圖3 C8+e∪P3的優(yōu)美標(biāo)號(hào)

圖4 C8+e∪P3的優(yōu)美標(biāo)號(hào)

圖5 C8+e∪P3的優(yōu)美標(biāo)號(hào)

圖6 K2,5+e∪C3的優(yōu)美標(biāo)號(hào)

圖7 K2,5+e∪C4的優(yōu)美標(biāo)號(hào)

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

[2] 楊顯文.關(guān)于C4m蛇的優(yōu)美性[J].工程數(shù)學(xué)學(xué)報(bào)，1995,12(4):108-112.

[3] 吳躍生.關(guān)于圈C4h的(r1,r2,...,r4h)-冠的優(yōu)美性[J].華東交通大學(xué)學(xué)報(bào),2011,28(1):77-80.

[4] 吳躍生,李詠秋.關(guān)于圈C4h+3的(r1,r2,...,r4h+3)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào)：自然科學(xué)版,2011,32(6):1-4.

[9] 吳躍生.圖C7(r1,r2,r3,r4,r5,0,0)∪St(m)的優(yōu)美性[J] 吉首大學(xué)學(xué)報(bào)：自然科學(xué)版,2012,33(5):9-11.

[10] 吳躍生,王廣富，徐保根.非連通圖C2n+1∪Gn-1的優(yōu)美性[J].華東交通大學(xué)學(xué)報(bào),2012,29(6):26-29.

[11] 吳躍生.關(guān)于圈C4h+3的(Gr1,Gr2,...,Gr4h+3)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào)：自然科學(xué)版,2013,34(4):4-9.

(責(zé)任編輯 向陽潔)

GracefulnessofUnconnectedGraphG+e∪Hk-1

WU Yuesheng

(School of Basic Sciences,East China Jiaotong University,Nanchang 330013,China)

It is proved that ifk≥2 then unconnected graphG+e∪Hk-1is a graceful graph,whereGis balanced bipartite graph andHk-1is a graceful graph withk-1 edges.

graceful graph;unconnected graph;balanced bipartite graph

1007-2985(2014)02-0003-03

2013-06-29

國(guó)家自然科學(xué)基金資助項(xiàng)目(11261019,11061014)；江西省自然科學(xué)基金資助項(xiàng)目(20114BAB201010)

吳躍生(1959-)，男，江西瑞金人，華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院副教授，碩士，主要從事圖論研究.

O157.5

A

10.3969/j.issn.1007-2985.2014.02.002