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

吳躍生，王廣富，徐保根

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

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

吳躍生，王廣富，徐保根

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

優美圖；聯圖；非連通圖；冠

1 預備知識

圖的標號問題是組合數學中一個熱門課題.[1-12]它不僅屬于圖論領域，也屬于設計理論的范疇，主要應用于編碼設計、變壓器箱設計、雷達脈沖、射電天文學、通訊網絡、晶體結構中原子位置的測定和導彈控制碼等研究.

本文所討論的圖均為無向簡單圖，V(G)和E(G)分別表示圖G的頂點集和邊集.為了簡單起見，我們把一個有p個頂點q條邊的圖記為(p，q)-圖.記號[m，n]表示整數集合{m，m+1，m+2，…，n}，其中m和n均為非負整數，且滿足0≤m

定義1[1]對于一個圖G=(V，E)，如果存在一個單射θ：V(G)→{0，1，2，…，|E(G)|}，使得對所有邊e=(u，v)∈E(G)，由θ′(e)=|θ(u)-θ(v)|導出的E(G)→{1，2，…，|E(G)|}是一個雙射，則稱G是優美圖，θ是G的一個優美標號，稱θ′為G邊上由θ導出的誘導值.

定義2[1]設f為G的一個優美標號，如果存在一個正整數k，使得對任意的uv∈E(G)有

f(u)>k≥f(v)(或f(u)≤k

成立，則稱f為G的平衡標號(或稱G有平衡標號f)，且稱k為f的特征.圖G稱為平衡二分圖(balanced bipartite graph).

顯然，若f為G的平衡標號，則k是邊導出標號為1的邊的兩個端點中標號較小的頂點的標號.

定義3[1]在平衡二分圖G中，設其優美標號θ的特征為k，并且θ(u0)=k，θ(v0)=k+1，則稱u0為G的二分點，v0為G的對偶二分點.

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

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

頂點y1粘接了r1條懸掛邊，頂點y2粘接了r2條懸掛邊，頂點xi粘接了r2+i條懸掛邊.

2 主要結果及其證明

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

引理2 當k≥2時，(p，q)-圖G是特征為k的平衡二分圖，Hk-1是邊數為k-1的優美圖，則非連通圖G+e∪Hk-1是優美的.

證明 設V(G)劃分成兩個集合X，Y；v1，v2∈X，θ是圖G的平衡標號，且θ(v1)=0，θ(v2)=k，即v2是平衡二分圖G的二分點，e=v1v2.

下面證明標號θ1是圖G+e∪Hk-1的優美標號.

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

是一個單(或雙)射.

因此θ1是圖G+e∪Hk-1的優美標號.證畢.

引理3 對任意自然數

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

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

證明 設V(Km，n)={x1，x2，…，xm，y1，y2，…，yn}，與xi鄰接的端點(或葉)記為xi，j，i=1，2，…，m；j=1，2，…，ri.與y1鄰接的端點(或葉)記為y1，j，j=1，2，…，rm+1.與yn鄰接的端點(或葉)記為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)-冠的頂點標號θ為：

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

當rm+1=0時，

θ(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；

當ri=0時，

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

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

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

當rm+n=0時，

θ(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)-冠的平衡標號

下面證明標號θ是圖Km，n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠的優美標號.

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

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

(2) 由點標號θ導出的邊標號θ′為：

θ′(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|.

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

令

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)-冠是平衡二分圖(交錯圖)，且圖Km+n的(r1，r2，…，rm+1，0，0，…，0，rm+n)-冠關于平衡標號θ的特征為rm+1+rm+n+m-1.證畢.

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

引理4 對任意自然數m≥2，ri(i=1，2，…，m+2)，Km，2(r1，r2，…，rm+2)是平衡二分圖(交錯圖)，且Km，2(r1，r2，…，rm+2)關于平衡標號θ的特征為rm+1+rm+2+m-1.

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

圖3 K5，2(1，2，3，5，6，7)的第一種平衡標號

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

證明 設θ1是引理4所給出的圖Kn，2(r1，r2，…，rn+2)的平衡標號(如圖3)，圖Kn，2(r1，r2，…，rn+2)的頂點集如圖1所示，則有圖Kn，2(r1，r2，…，rn+2)關于平衡標號θ1的特征為

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

即頂點y2是圖Kn，2(r1，r2，…，rn+2)關于平衡標號θ1的對偶二分點.令

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

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

即頂點y2是圖kn，2(r1，r2，…，rn+2)關于平衡標號θ2的二分點.由引理2可知，

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

圖5 圖的優美標號

圖6 圖的優美標號

[1] 馬克杰.優美圖[M].北京：北京大學出版社，1991：1-247.

[2] 楊顯文.關于C4m蛇的優美性[J].工程數學學報，1995，12(4)：108-112.

[3] 吳躍生.關于圈C4h的(r1，r2，r4h)-冠的優美性[J].華東交通大學學報，2011，28(1)：77-80.

[4] 吳躍生，李詠秋.關于圈C4h+3的(r1，r2，…，r4h)-冠的優美性[J].吉首大學學報：自然科學版，2011，32(6)：1-4.

[8] 魏麗俠，張昆龍.幾類并圖的優美標號[J].中山大學學報：自然科學版，2008，47(3)：10-13.

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

[10] 張家娟，郭珠霞，周向前，等.優美圖的一些性質[J].數學的實踐與認識，2012，42(13)：197-201.

[11] 張志尚，黃文強，東愷.兩類并圖的優美標號[J].東北師大學報：自然科學版，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

(責任編輯：陶 理)

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

國家自然科學基金資助項目(11261019，11361024)；江西省自然科學基金資助項目(20114BAB201010).

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

O 157.5 [學科代碼] 110·7470

A