吳躍生，王廣富，徐保根

(華東交通大學(xué)理學(xué)院，江西 南昌 330013)

非連通圖(P2∨)(r1，r2，…，rn+2)∪Gr的優(yōu)美性

吳躍生，王廣富，徐保根

(華東交通大學(xué)理學(xué)院，江西 南昌 330013)

優(yōu)美圖；聯(lián)圖；非連通圖；冠

1 預(yù)備知識(shí)

圖的標(biāo)號(hào)問(wèn)題是組合數(shù)學(xué)中一個(gè)熱門課題.[1-12]它不僅屬于圖論領(lǐng)域，也屬于設(shè)計(jì)理論的范疇，主要應(yīng)用于編碼設(shè)計(jì)、變壓器箱設(shè)計(jì)、雷達(dá)脈沖、射電天文學(xué)、通訊網(wǎng)絡(luò)、晶體結(jié)構(gòu)中原子位置的測(cè)定和導(dǎo)彈控制碼等研究.

本文所討論的圖均為無(wú)向簡(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

定義1[1]對(duì)于一個(gè)圖G=(V，E)，如果存在一個(gè)單射θ：V(G)→{0，1，2，…，|E(G)|}，使得對(duì)所有邊e=(u，v)∈E(G)，由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的E(G)→{1，2，…，|E(G)|}是一個(gè)雙射，則稱G是優(yōu)美圖，θ是G的一個(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)(或稱G有平衡標(biāo)號(hào)f)，且稱k為f的特征.圖G稱為平衡二分圖(balanced bipartite graph).

顯然，若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).

定義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).

定義5v1和v2是圖G的兩個(gè)不相鄰的頂點(diǎn)，連接v1和v2，使圖G增加一條邊，所得到的圖，稱為圖G(v1，v2).

定義6[5-6]V(G)={v1，v2，…，vn}中的每個(gè)頂點(diǎn)vi都粘接了ri條懸掛邊(ri為自然數(shù)，i=1，2，…，n)所得到的圖，稱為圖G的(r1，r2，…，rn)-冠，簡(jiǎn)記為G(r1，r2，…，rn).特別的，當(dāng)r1=r2=…=rn=r時(shí)，稱為圖G的r-冠.圖G的0-冠就是圖G.

頂點(diǎn)y1粘接了r1條懸掛邊，頂點(diǎn)y2粘接了r2條懸掛邊，頂點(diǎn)xi粘接了r2+i條懸掛邊.

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.

引理2 當(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)劃分成兩個(gè)集合X，Y；v1，v2∈X，θ是圖G的平衡標(biāo)號(hào)，且θ(v1)=0，θ(v2)=k，即v2是平衡二分圖G的二分點(diǎn)，e=v1v2.

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

θ1：V(G+e∪Hk-1)=V(G)∪V(Hk-1)→[0，q+k]

是一個(gè)單(或雙)射.

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

引理3 對(duì)任意自然數(shù)

m≥2，n≥2，ri(i=1，2，…，m+1，m+n)，km，n(r1，r2，…，rm+1，0，0，…，rm+n)

是平衡二分圖(交錯(cuò)圖).

證明 設(shè)V(Km，n)={x1，x2，…，xm，y1，y2，…，yn}，與xi鄰接的端點(diǎn)(或葉)記為xi，j，i=1，2，…，m；j=1，2，…，ri.與y1鄰接的端點(diǎn)(或葉)記為y1，j，j=1，2，…，rm+1.與yn鄰接的端點(diǎn)(或葉)記為yn，j，j=1，2，…，rm+n.圖Km，n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠如圖1所示.

定義圖的(r1，r2，…，rm+1，0，0，…，rm+n)-冠的頂點(diǎn)標(biāo)號(hào)θ為：

θ(y1，i)=i-1，i=1，2，…，rm+1.

當(dāng)rm+1=0時(shí)，

θ(y1，i)=θ(y1)；

θ(xi)=θ(y1，rm+1)+i=rm+1-1+i，i=1，2，…，m；

θ(yi)=θ(y1)-(i-1)m，i=2，…，n-1；

當(dāng)ri=0時(shí)，

θ(xi，j)=θ(xi)；

θ(yn)=θ(x1，1)-1=rm+1+rm+n+m；

θ(yn，j)=θ(xm)+j，j=1，2，…，rm+n.

當(dāng)rm+n=0時(shí)，

θ(yn，j)=θ(yn).

圖1 Km，n的(r1，r2，…，rm+1，0，0，…，rm+n)-冠

圖2 K5，3的(1，2，3，4，5，6，0，7)-冠的平衡標(biāo)號(hào)

下面證明標(biāo)號(hào)θ是圖Km，n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠的優(yōu)美標(biāo)號(hào).

(1) 由于

0=θ(y1，1)<θ(y1，2)<…<θ(y1，rm+1)<θ(x1)<θ(x2)<…<
θ(xm)<θ(yn，1)<θ(yn，2)<…<θ(yn，rm+n-1)<θ(yn，rm+n)<θ(yn)<
θ(x1，1)<θ(x1，2)<…<θ(x1，r1)<θ(x2，1)<θ(x2，2)<…<θ(x2，r1)<
θ(x3，1)<θ(x3，2)<…<θ(x3，3)<…<θ(xm，1)<θ(xm，2)<…<θ(xm，rm)<
θ(yn-1)<θ(yn-2)<…<θ(y1)=|E|.

容易驗(yàn)證V(Km，n(r1，r2，…，rm+1，0，0，…，0，rm+n))→{0，1，2，…，|E|}是一個(gè)單射.

(2) 由點(diǎn)標(biāo)號(hào)θ導(dǎo)出的邊標(biāo)號(hào)θ′為：

θ′(y1y1，i)=|E|+1-i，i=1，2，…，rm+1.

θ′(y1xi)=|E|-rm+1+1-i，i=1，2，…，m.

θ′(yixj)=|E|-(i-1)m-rm+1+1-j，i=2，…，n-1；j=1，2，…，m.

θ′(ynxi)=m+1+rm+n-i，i=1，2，…，m.

由于

1=θ′(ynyn，1)<θ′(ynyn，2)<…<θ′(ynyn，rm+n)<θ′(ynxm)<θ′(ynxm-1)<…<
θ′(ynx1)<θ′(x1x1，1)<θ′(x1x1，2)<…<θ′(x1x1，r1)<θ′(x2x2，1)<θ′(x2x2，2)<…<
θ′(x2x2，r2)<…<θ′(xmxm，1)<θ′(xmxm，2)<…<θ′(xmxm，rm)<θ′(xmyn-1)<
θ′(xm-1xn-1)<…<θ′(x1yn-1)<θ′(xmyn-2)<θ′(xm-1yn-2)<…<θ′(x1yn-2)<…<
θ′(xmy1)<θ′(xm-1y1)<θ′(x1y1)<θ′(y1y1，rm+1)<θ′(y1y1，rm+1-1)<…<θ′(y1y1，2)=|E|.

容易驗(yàn)證θ′：E(Km，n(r1，r2，…，rm+1，0，0，…，0，rm+n))→{0，1，2，…，|E|}是一個(gè)雙射.因此θ是圖Km，n的(r1，r2，…，rm+1，0，0，…，rm+n)-冠的優(yōu)美標(biāo)號(hào).

令

X={y1，1，y1，2，…，y1，rm+1，x1，x2，xm，yn，1，yn，2，…，yn，rm+n}，

Y=V(Km，n(r1，r2，…，rm+1，0，0，…，0，rm+n))-X，

有

故圖Km，n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠是平衡二分圖(交錯(cuò)圖)，且圖Km+n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠關(guān)于平衡標(biāo)號(hào)θ的特征為rm+1+rm+n+m-1.證畢.

圖K5，3的(1，2，3，4，5，6，0，7)的平衡標(biāo)號(hào)如圖2所示.

引理4 對(duì)任意自然數(shù)m≥2，ri(i=1，2，…，m+2)，Km，2(r1，r2，…，rm+2)是平衡二分圖(交錯(cuò)圖)，且Km，2(r1，r2，…，rm+2)關(guān)于平衡標(biāo)號(hào)θ的特征為rm+1+rm+2+m-1.

圖K5，2(1，2，3，4，5，6，7)的兩種平衡標(biāo)號(hào)如圖3—4所示.

圖3 K5，2(1，2，3，5，6，7)的第一種平衡標(biāo)號(hào)

圖4 K5，2的(1，2，3，4，5，6，7)的第二種平衡標(biāo)號(hào)

證明 設(shè)θ1是引理4所給出的圖Kn，2(r1，r2，…，rn+2)的平衡標(biāo)號(hào)(如圖3)，圖Kn，2(r1，r2，…，rn+2)的頂點(diǎn)集如圖1所示，則有圖Kn，2(r1，r2，…，rn+2)關(guān)于平衡標(biāo)號(hào)θ1的特征為

rn+1+rn+2+n-1，θ1(y1)=|E(Kn，2(r1，r2，…，rn+2))|，θ1(y2)=rn+1+rn+2+n，

即頂點(diǎn)y2是圖Kn，2(r1，r2，…，rn+2)關(guān)于平衡標(biāo)號(hào)θ1的對(duì)偶二分點(diǎn).令

θ2=|E(Kn，2(r1，r2，…，rn+2))|-θ1，

由引理1可知，θ2是圖Kn，2(r1，r2，…，rn+2)的另一種平衡標(biāo)號(hào)(如圖4)，則有圖Kn，2(r1，r2，…，rn+2)關(guān)于平衡標(biāo)號(hào)θ2的特征為

即頂點(diǎn)y2是圖kn，2(r1，r2，…，rn+2)關(guān)于平衡標(biāo)號(hào)θ2的二分點(diǎn).由引理2可知，

在定理1中，令ri=0，i=1，2，…，n+2，有如下的結(jié)論：

圖5 圖的優(yōu)美標(biāo)號(hào)

圖6 圖的優(yōu)美標(biāo)號(hào)

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

[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)-冠的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，32(6)：1-4.

[8] 魏麗俠，張昆龍.幾類并圖的優(yōu)美標(biāo)號(hào)[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，47(3)：10-13.

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

[10] 張家娟，郭珠霞，周向前，等.優(yōu)美圖的一些性質(zhì)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42(13)：197-201.

[11] 張志尚，黃文強(qiáng)，東愷.兩類并圖的優(yōu)美標(biāo)號(hào)[J].東北師大學(xué)報(bào)：自然科學(xué)版，2013，45(2)：30-34.

[12] GALLIAN J A.A dynamic survey of graph labeling[J].The Electronic Journal of Combinatorics，2013，16(DS6)：1-308.

Keywords:graceful graph；join graph；disconnected graph；corona

(責(zé)任編輯：陶 理)

WU Yue-sheng，WANG Guang-fu，XU bao-gen

(School of Science，East China Jiaotong University，Nanchang 330013，China)

1000-1832(2014)03-0038-05

10.11672/dbsdzk2014-03-008

2013-01-05

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

吳躍生(1959—)，男，碩士，副教授，主要從事圖論研究.

O 157.5 [學(xué)科代碼] 110·7470

A