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

吳躍生

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

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

吳躍生

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

討論了非連通圖C4m-1∪G的優(yōu)美性，給出了非連通圖C4m-1∪G是優(yōu)美圖的2個(gè)充分條件.

優(yōu)美圖;交錯(cuò)圖；非連通圖;優(yōu)美標(biāo)號(hào)

1 相關(guān)定義

文中所討論的圖均為無(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-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).

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

定理1 對(duì)任意正整數(shù)m，若圖G是特征為k且缺k+3m-1標(biāo)號(hào)值的交錯(cuò)圖(3m-1≤k+3m-1≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號(hào)值k+1的優(yōu)美標(biāo)號(hào).

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

θ(x2i)=4m-i+k,i=1,2,…,2m-1;θ(x2i-1)=i+k+1,i=1,2,…,m;

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

(ⅰ)θ:X→[0,k]是單射(或雙射);θ:Y→[k+4m,q+4m-1]-{7m-2+k}是單射(或雙射);θ:V(C4m-1)→[k+2,k+4m-1]∪{7m-2+k}是單射(或雙射);θ:V(C4m-1∪G)→[0,q+4m-1]-{k+1}是單射.

(ⅱ)

θ′(x2m+2x2m+1)=4m-1；

θ′(x2mx2m+1)=4m-2；θ′(x4m-1x1)=2m-2.

θ′:E(C4m-1)→[1,4m-1]是雙射；θ′:E(G)→[4m,q+4m-1]是雙射.θ′：E(C4m-1∪G)→[1,q+4m-1]是一一對(duì)應(yīng).

由(ⅰ)和(ⅱ)可知，θ就是非連通圖C4m-1∪G的缺k+1標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).證畢.

定理2 對(duì)任意正整數(shù)m，若圖G是特征為k且缺k+m+1標(biāo)號(hào)值的交錯(cuò)圖(m+1≤k+m+1≤|E(G)|)，則非連通圖C4m-1∪G存在缺標(biāo)號(hào)值k+1,特征為2m+k+1的優(yōu)美標(biāo)號(hào).

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

(ⅰ)θ:X→[0,k]，θ:Y→[k+4m,q+4m-1]-{k+5m}，θ:V(C4m-1)→[k+2,k+4m-1]∪{k+5m}均為單射(或雙射);θ:V(C4m-1∪G)→[0,q+4m-1]-{k+1}為單射.

(ⅱ)

θ′(x2m-1x2m)=4m-1；

θ′(x2mx2m+1)=4m-2；θ′(x4m-1x1)=2m-1.

θ′:E(C4m-1)→[1,4m-1]，θ′:E(G)→[4m,q+4m-1]均為雙射.θ′：E(C4m-1∪G)→[1,q+4m-1]是一一對(duì)應(yīng).

由(ⅰ)和(ⅱ)可知θ就是非連通圖C4m-1∪G的缺k+1標(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).

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

注意到3n=(2n-1)+n+1，由定理1和引理1有以下結(jié)論：

推論1 對(duì)任意正整數(shù)m，非連通圖C4m-1∪C12m-8存在缺標(biāo)號(hào)值6m-4的優(yōu)美標(biāo)號(hào).

例1 非連通圖C7∪C16存在缺標(biāo)號(hào)值8的優(yōu)美標(biāo)號(hào)為:非連通圖C7∪C16中C7的優(yōu)美標(biāo)號(hào)為9,14,10,13,19,12,11,9;非連通圖C7∪C16中C16的優(yōu)美標(biāo)號(hào)為0,23,1,22,2,21,3,20,4,18,5,17,6,16,7,15,0.

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

推論2 對(duì)任意正整數(shù)m，非連通圖C4m-1∪C4m存在缺2m標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).

例2 由推論2給出的非連通圖C11∪C12的缺標(biāo)號(hào)值6的優(yōu)美標(biāo)號(hào)為7,16,8,15,9,20,10,14,11,13,12,7;0,23,1,22,2,21,3,19,4,18,5,17,0.

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

[11] GALLIAN J A.A Dynamic Survey of Graph Labeling[J].The Electronic Journal of Combinatorics，2013,16(DS6)：1-308.

(責(zé)任編輯 向陽(yáng)潔)

GracefulLabelingoftheUnconnectedGraphC4m-1∪G

WU Yuesheng

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

The gracefulness of the unconnected graphC4m-1∪Gis discussed.Two sufficient conditions are given for the gracefulness of unconnected graphC4m-1∪G.

graceful graph;balanced bipartite graph;unconnected graph;graceful labeling

1007-2985(2014)03-0001-03

2013-10-25

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

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

O157.5

A

10.3969/j.issn.1007-2985.2014.03.001