吳躍生，王廣富

非連通圖12(1,0,2,0,3,0,…,0)∪的優(yōu)美標(biāo)號(hào)

*吳躍生，王廣富

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

討論了非連通圖12(1,0,2,0,3,0,…,0)∪的優(yōu)美性，給出了非連通圖12(1,0,2,0,3,0,…,0)∪是優(yōu)美圖的一個(gè)充分條件。

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

1 引言與概念

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

成立，則稱為的平衡標(biāo)號(hào)(或稱有平衡標(biāo)號(hào))，且稱為的特征。圖稱為平衡二分圖（balanced bipartite graph）。

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

定義5[3-4]()={1,2,…,n}的每個(gè)頂點(diǎn)i都粘接了r條懸掛邊(r為自然數(shù)，=1, 2,…,)所得到的圖，稱為圖的1,2,…,r)-冠，簡(jiǎn)記為1,2,…,r)。特別地，當(dāng)1=2=… =r=時(shí)，稱為圖的-冠。圖的0-冠就是圖。

文[1]給出了圖12的交錯(cuò)標(biāo)號(hào)。本文討論了非連通圖12(1,0,2,0,3,0,…,0)∪的優(yōu)美性。

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

令={13,5,7,9,11}∪1，={24,6, u, u10,12}∪{yi,j|1,2,3,j= r}∪1

則有

引理1[3]對(duì)任意自然數(shù)1，2，3，4,12(1,02,03,0,4, 00,000)) 存在特征值為5且缺標(biāo)號(hào)值9的交錯(cuò)標(biāo)號(hào)。

令={13,5, u u9,11},={24,6, u u10,12}∪{y2i-1,j|1,2,341,2,…,r}則有

由定理和引理1，有

推論2對(duì)任意自然數(shù)r(=1,2,…,7),則非連通圖12(1,0,2,0,3,0,…,0)∪12(4,05,06,0,7,00,000)存在缺標(biāo)號(hào)值6的特征為12交錯(cuò)標(biāo)號(hào)。

引理2對(duì)任意自然數(shù)1,4(1,22,2)存在特征值為5且缺標(biāo)號(hào)值9的交錯(cuò)標(biāo)號(hào)。

令={1，3，2,1，2,2，4,1，4,2}，={24,}∪ {1, j|12…,1}∪{3,1,3,2}則有

由引理2和定理，有

推論3對(duì)任意自然數(shù)r(=1,2,3,4)非連通圖12(1,0,2,0,3,0,…,0)∪4(4,22,2 )存在缺標(biāo)號(hào)值6的特征為12交錯(cuò)標(biāo)號(hào)。

引理3[1]對(duì)任意自然數(shù)，, 當(dāng)≥4，≥2時(shí)，完備二分圖K存在特征為1且缺m+3標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

證設(shè)完備二分圖K的頂點(diǎn)二分劃為1，2，1={1,2,…,m},2={1,2,…,u}。

容易驗(yàn)證：對(duì)任意自然數(shù)，,當(dāng)≥4，≥2時(shí)，完備二分圖K存在特征為1且缺m+3標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

由引理3和定理，有

推論4 對(duì)任意自然數(shù)r(=1,2,3),,,當(dāng)≥4，≥2時(shí), 非連通圖12(1,0,2,0,3,0,…,0)∪K存在缺標(biāo)號(hào)值的特征為4交錯(cuò)標(biāo)號(hào)。

引理4 對(duì)任意自然數(shù)r(=1,2)，當(dāng)2≥1時(shí)，非連通圖8(1,0,2,0,2,0,2,0)存在缺標(biāo)號(hào)值7的特征為3交錯(cuò)標(biāo)號(hào)。

Ⅰ 當(dāng)2=1時(shí)

令={13,5, u},

={24,6, u}∪{y1,j|1,2,…1}∪

{y2,1, y3,1,y4,1}

則有

Ⅱ 當(dāng)2≥2時(shí)

令={13,5, u},={24,6, u}∪

{1,j1,2,1}∪{y2, 3,4,1,2,…,2}

則有

由引理4和定理，有

推論5 對(duì)任意自然數(shù)r(=1,2,3,4,5), r≥1,非連通圖12(1,0,2,0,3,0,…,0)∪8(4,05,0,5,0,5,0)存在缺標(biāo)號(hào)值4的特征為10交錯(cuò)標(biāo)號(hào)。

圖1 ∪C12(1,0,2,0,3,0,4,0,0,0,0,0)的交錯(cuò)標(biāo)號(hào)

圖2 C12(1,0,3,0,2,0,0,…,0) ∪C12(1,0,2,0,3,0,4,0,0,0,0,0)的交錯(cuò)標(biāo)號(hào)

圖3 C12(1,0,3,0,2,0,0,…,0) ∪C4(8,2,2,2)的交錯(cuò)標(biāo)號(hào)

圖4 C12(2,0, 2,0, 2,0,0,…,0) ∪K42的交錯(cuò)標(biāo)號(hào)

圖5 C12(3,0, 0,0, 3,0,0,…,0) ∪C8(6,0, 1,0, 1,0,1,0)的交錯(cuò)標(biāo)號(hào)

圖612(1,0, 4,0, 2,0,0,…,0) ∪8(5,0, 2,0, 2,0,2,0)的交錯(cuò)標(biāo)號(hào)

Fig.6 The altemating labeling of12(1,0, 4,0, 2,0,0,…,0) ∪8(5,0, 2,0, 2,0,2,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的(1,2,…,4h)-冠的優(yōu)美性[J].華東交通大學(xué)學(xué)報(bào),2011,28(1):77-80.

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

[5] 吳躍生.關(guān)于圖6k+53∪P3的優(yōu)美性[J] 吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2012,33(3):4-7.

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

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

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

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

The graceful labeling of the unconnected graph12(1,02,0,r,0,…,0)∪

*WU Yue-sheng WANG Guang-fu

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

The gracefulness of the Graph121020300∪are discussed. One sufficient conditionsis given for the gracefulness of unconnected graph121020300∪

graceful graph;unconnected graph; balanced bipartite graph

O159.1

A

10.3969/j.issn.1674-8085.2014.02.001

1674-8085(2014)02-0001-06

2013-12-09；

2014-01-11

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

*吳躍生(1959-)，男，江西瑞金人，副教授，碩士，主要從事圖論研究(E-mail: 616100567@qq.com);

王廣富(1976-)，男，山東荷澤人，副教授，博士，主要從事圖論研究(E-mail:wgfmath@126.com).