非連通圖D4∪G的優(yōu)美標(biāo)號(hào)

吳躍生

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

非連通圖D4∪G的優(yōu)美標(biāo)號(hào)

吳躍生

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

討論了非連通圖D4∪G的優(yōu)美性，給出了非連通圖D4∪G是優(yōu)美圖的3個(gè)充分條件。

優(yōu)美圖;交錯(cuò)圖；非連通圖;優(yōu)美標(biāo)號(hào);荷蘭m-風(fēng)車

1 引言與概念

本文所討論的圖均為無(wú)向簡(jiǎn)單圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集，記號(hào)[m,n]表示整數(shù)集合{m,m+1,…,n}，其中m和n均為非負(fù)整數(shù)，且滿足0≤m

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

定義1[1]由m個(gè)完備圖K3的恰有一個(gè)公共點(diǎn)所構(gòu)成的圖成為荷蘭m-風(fēng)車(Dutchm-wind-mill)，記作Dm[1]。

文獻(xiàn)[1]已指出：Dm是優(yōu)美圖的充要條件為：m=0,1(mod4)。

本文討論非連通圖D4∪G的優(yōu)美性。

定義2[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)值。

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

成立，則稱f為G的平衡標(biāo)號(hào)(或稱G有平衡標(biāo)號(hào)f)，且稱k為f的特征。圖G稱為平衡二分圖(balancedbipartitegraph)。

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

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

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

定理 1 如果圖G是特征為k且缺k+2標(biāo)號(hào)值的交錯(cuò)圖(2≤k+2≤|E(G)|)，則非連通圖D4∪G存在缺k+1、k+7、k+8和k+9標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

圖1 荷蘭風(fēng)車圖D4Fig.1 Dutch wind-mill D4

定義D4∪G的頂點(diǎn)標(biāo)號(hào)θ為：

θ(v1)=k+2，θ(v2)=k+6，θ(v3)=k+12，

θ(v4)=k+3，θ(v5)=k+14,θ(v6)=k+5，

θ(v7)=k+10，θ(v8)=k+4，θ(v9)=k+11，

下面證明θ是非連通圖D4∪G的優(yōu)美標(biāo)號(hào)。

(1)θ:X→[0, k]是單射(或雙射);θ:Y→[k+13,q+12]-{k+14}是單射(或雙射);

θ:V(D4)→[k+2,k+12]∪{k+14}-{k+7,k+8,k+9}是雙射;

容易驗(yàn)證：θ:V(D4∪G)→[0,q+12]-{k+1,k+7,k+8,k+9}是單射(或雙射)。

(2)θ′(v1v2)=|θ(v1)-θ(v2)|=4,

θ′(v1v3)=10,θ′(v2v3)=6, θ′(v1v4)=1,

θ′(v1v5)=12,θ′(v4v5)=11,θ′(v6v1)=3,

θ′(v7v1)=8, θ′(v6v7)=5, θ′(v8v1)=2,

θ′(v9v1)=9, θ′(v8v9)=7。

θ′:E(D4)→[1,12]是雙射；

θ′:E(G)→[13,q+12]是雙射。

θ′：E(D4∪G)→[1,q+12]是一一對(duì)應(yīng)。

由(1)和(2)可知,θ就是非連通圖D4∪G的缺k+1、k+7、k+8和k+9標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

定理 2 如果圖G是特征為k且缺k+10標(biāo)號(hào)值的交錯(cuò)圖(10≤k+10≤|E(G)|)，則非連通圖D4∪G存在缺k+4、k+5、k+6和k+12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D4∪G的頂點(diǎn)標(biāo)號(hào)θ為：

θ(v1)=k+11，θ(v2)=k+1， θ(v3)=k+7，

θ(v4)=k+10，θ(v5)=k+22,θ(v6)=k+8，

θ(v7)=k+3， θ(v8)=k+9，θ(v9)=k+2，

下面證明θ是非連通圖D4∪G的優(yōu)美標(biāo)號(hào)。

(1)θ:X→[0, k]是單射(或雙射);θ:Y→[k+13,q+12]-{k+22}是單射(或雙射);

θ:V(D4)→[k+1,k+11]∪{k+22}-{k+4,k+5,k+6}是雙射;

容易驗(yàn)證：θ: V(D4∪G)→[0,q+12]-{k+4,k+5,k+6,k+12}是單射(或雙射)。

(2)θ′(v1v2)=|θ(v1)-θ(v2)|=10,

θ′(v1v3)=4, θ′(v2v3)=6,θ′(v1v4)=1,

θ′(v1v5)=11,θ′(v4v5)=12,θ′(v6v1)=3,

θ′(v7v1)=8, θ′(v6v7)=5,θ′(v8v1)=2,

θ′(v9v1)=9, θ′(v8v9)=7。

θ:E(D4)→[1,12]是雙射；

θ′:E(G)→[13,q+12]是雙射。

θ′：E(D4∪G)→[1,q+12]是一一對(duì)應(yīng)。

由(1)和(2)可知，θ就是非連通圖D4∪G的缺k+4、k+5、k+6和k+12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

定理 3 如果圖G是特征為k且缺k+11標(biāo)號(hào)值的交錯(cuò)圖(11≤k+11≤|E(G)|)，則非連通圖D4∪G存在缺k+1、k+5、k+6和k+7標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D4∪G的頂點(diǎn)標(biāo)號(hào)θ為：

θ(v1)=k+12，θ(v2)=k+2，θ(v3)=k+8，

θ(v4)=k+11，θ(v5)=k+23,θ(v6)=k+9，

θ(v7)=k+4，θ(v8)=k+10，θ(v9)=k+3，

下面證明θ是非連通圖D4∪G的優(yōu)美標(biāo)號(hào)。

(1)θ:X→[0, k]是單射(或雙射);θ:Y→[k+13,q+12]-{k+23}是單射(或雙射);

θ:V(D4)→[k+2,k+12]∪{k+23}-{k+5,k+6,k+7}是雙射;

容易驗(yàn)證：θ:V(D4∪G)→[0,q+12]-{k+1,k+5,k+6,k+7}是單射(或雙射)。

(2)θ′(v1v2)=|θ(v1)-θ(v2)|=10,

θ′(v1v3)=4,θ′(v2v3)=6, θ′(v1v4)=1,

θ′(v1v5)=11,θ′(v4v5)=12,θ′(v6v1)=3,

θ′(v7v1)=8,θ′(v6v7)=5,θ′(v8v1)=2,

θ′(v9v1)=9,θ′(v8v9)=7。

θ′:E(D4)→[1,12]是雙射；

θ′: E(G)→[13,q+12]是雙射。

θ′：E(D4∪G)→[1,q+12]是一一對(duì)應(yīng)。

由(1)和(2)可知，θ就是非連通圖D4∪G的缺k+1、k+5、k+6和k+7標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

引理1 對(duì)任意正整數(shù)n，設(shè)C4n是有4n個(gè)頂點(diǎn)的圈，則C4n存在特征為2n-1,且缺3n的交錯(cuò)標(biāo)號(hào)。

證明 記圈C4n上的頂點(diǎn)依次為v1，v2,…,v4n,定義圈C4n的頂點(diǎn)標(biāo)號(hào)θ為：

容易驗(yàn)證，θ就是圈C4n的特征為2n-1,且缺3n的交錯(cuò)標(biāo)號(hào)。

注意到：3n=(2n-1)+n+1，由定理1和引理1有：

推論1 非連通圖D4∪C4存在缺2、8、9和11標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D4∪C4的優(yōu)美標(biāo)號(hào)如圖2所示。

圖2 非連通圖D4∪C4的優(yōu)美標(biāo)號(hào)Fig.2 The graceful labeling of the graph D4∪C4

由定理2和引理1有：

推論2 非連通圖D4∪C36存在缺21、22、23和29標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D4∪C36中D4的優(yōu)美標(biāo)號(hào)如圖3所示。非連通圖D4∪C36中C36的優(yōu)美標(biāo)號(hào)為:0、48、

圖3 非連通圖D4∪C36中D4的優(yōu)美標(biāo)號(hào)Fig.3 The graceful labeling of the graph D4of the graph D4∪C36

1、47、2、46、3、45、4、44、5、43、6、42、7、41、8、40、9、38、10、37、11、36、12、35、13、34、14、33、15、32、16、31、17、30。

由定理3和引理1有：

推論3 非連通圖D4∪C40存在缺20、24、25和26標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D4∪C40中D4的優(yōu)美標(biāo)號(hào)如圖4所示。非連通圖D4∪C40中C40的優(yōu)美標(biāo)號(hào)為:0、52、1、51、2、50、3、49、4、48、5、47、6、46、7、45、8、44、9、43、10、41、11、40、12、39、13、38、14、37、15、36、16、35、17、34、18、33、19、32。

圖4 非連通圖D4∪C40中D4的優(yōu)美標(biāo)號(hào)Fig.4 The graceful labeling of the graph D4of the graph D4∪C40

引理2[1]當(dāng)m、n為任意自然數(shù)，且當(dāng)m≥2、n≥2時(shí)，完全二分圖Km,n存在特征m-1(或n-1)缺標(biāo)號(hào)值m+1(或n+1)的交錯(cuò)標(biāo)號(hào)。

由定理1和引理2有：

推論4 當(dāng)m、n為任意自然數(shù)，且當(dāng)m≥2、n≥2時(shí)，非連通圖Km,n∪D4存在缺標(biāo)號(hào)值m、m+6、m+7、m+8(或n、n+6、n+7、n+8)的優(yōu)美標(biāo)號(hào)。

例1 非連通圖K3,4∪D4存在缺2、8、9和10標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)如圖5所示。非連通圖K3,4∪D4存在缺3、9、10和11標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)如圖6所示。

圖5 非連通圖D4∪K3,4的第1種優(yōu)美標(biāo)號(hào)Fig.5 The first graceful labeling of the graph D4∪K2,4

圖6 非連通圖D4∪K3,4的第2種優(yōu)美標(biāo)號(hào)Fig.6 The second graceful labeling of the graph D4∪K2,4

例2 我們把圈C4的每一個(gè)頂點(diǎn)都粘接一個(gè)圖G,這樣所得到的圖稱為圈C4的G-冠。因?yàn)槿4的C4-冠存在特征為9缺11的交錯(cuò)標(biāo)號(hào),所以非連通圖(C4的C4-冠)∪D4存在缺10、

16、17和18標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào),非連通圖(C4的C4-冠)∪D4存在缺10、16、17和18標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)，如圖7所示。

圖7 非連通圖D4∪(C4的C4-冠)的優(yōu)美標(biāo)號(hào)Fig.7 The graceful labeling of the graph D4∪C4-corna of the cycle C4

[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.

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

[8] 吳躍生,王廣富，徐保根.關(guān)于C4h+1⊙K1的(Gr1,Gr2,…,Gr4h+1,Gr4h+2)-冠的優(yōu)美性[J].山東大學(xué)學(xué)報(bào),2013，48(4)：25-27.

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

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

(責(zé)任編輯：張英健)

The Graceful Labeling of the Unconnected GraphD4∪G

WU Yuesheng

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

The gracefulness of the unconnected graphD4∪Gis discussed. Three sufficient conditions are given for the gracefulness of unconnected graphD4∪G.

graceful graph; balanced bipartite graph; unconnected graph; graceful labeling; Dutchm-wind-mill

2014-05-09

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

吳躍生(1959-)，男，江西瑞金人，副教授，碩士，主要研究方向?yàn)閳D論。

O157.5

A

1671-5322(2014)04-0009-04