吳 躍 生

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

?

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

吳 躍 生

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

摘要:討論了非連通圖D2,4∪G的優(yōu)美性,給出了非連通圖D2,4∪G是優(yōu)美圖的六個(gè)充分條件.證明了非連通圖D2,4∪G(k)+a(a=2,3,4,5,6,7)都是優(yōu)美的.

關(guān)鍵詞:優(yōu)美圖; 交錯(cuò)圖; 非連通圖; 優(yōu)美標(biāo)號(hào)

記號(hào)V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集,m和n均為非負(fù)整數(shù),且滿足0≤m

圖的優(yōu)美標(biāo)號(hào)問題是組合數(shù)學(xué)中一個(gè)熱門課題[1-13].文獻(xiàn)[4-13]研究了非連通圖的優(yōu)美性,文獻(xiàn)[4]研究了非連通圖C4m∪G的優(yōu)美性;文獻(xiàn)[6-8]研究了非連通圖C4m-1∪G的優(yōu)美性;文獻(xiàn)[9-10]分別研究了非流通圖D2,6∪G和非流通圖D2,8∪G的優(yōu)美標(biāo)號(hào);文獻(xiàn)[11-13]研究了非連通圖C4m-1∪C12m-8∪G的優(yōu)美性.

1相關(guān)概念

定義1[1]對(duì)于一個(gè)圖G=(V,E),稱G是優(yōu)美圖,θ是G的一組優(yōu)美標(biāo)號(hào)是指:如果存在一個(gè)單射θ: V(G)→[0, |E(G)|]使得對(duì)所有邊e=uv∈E(G),由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的E(G)→[1,|E(G)|]是一個(gè)雙射.

把任意m個(gè)圈Cn的恰有一個(gè)公共點(diǎn)所組成的圖記作Dm,n[1].

D2,4存在特征為2,且 缺4和7標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào),如圖1所示,為方便記,把如圖1所示的標(biāo)號(hào)記為:(1:8,0,6;5,2,3)

圖1　圖D2,4的交錯(cuò)標(biāo)號(hào)

本文討論了非連通圖D2,4∪G的優(yōu)美性.

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

定理1當(dāng)2≤k+2≤|E(G(k)+2)|)時(shí),非連通圖D2,4∪G(k)+2存在下列標(biāo)號(hào):

(1) 特征為k+4且缺k+1和k+6標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào);

(2) 特征為k+3且缺k+6和k+8標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào);

(3) 缺k+3和k+7標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(4) 缺k+1和k+5標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).

圖2　圖D2,4

非連通圖D2,4∪G(k)+2的各種頂點(diǎn)標(biāo)號(hào)θ定義為

下面證明第一種標(biāo)號(hào)θ是非連通圖D2,4∪G(k)+2的優(yōu)美標(biāo)號(hào).

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

θ:V(D2,4)→[k+2,k+10]-{k+6,k+9}是雙射;

容易驗(yàn)證:θ: V(D2,4∪G(k)+2)→[0, q+8]-{k+1,k+6}是單射.

(2) θ′(v1v2)=|θ(v1)-θ(v2)|=6,θ′(v2v3)=|θ(v2)-θ(v3)|=5,θ′(v1v4)=|θ(v1)-θ(v4)|=8,

θ′(v3v4)=|θ(v3)-θ(v4)|=7,θ′(v3v5)=|θ(v3)-θ(v5)|=4,θ′(v5v6)=|θ(v5)-θ(v6)|=3,

θ′(v3v7)=|θ(v3)-θ(v7)|=2,θ′(v6v7)=|θ(v6)-θ(v7)|=1,

θ′:E(D2,4)→[1,8]是雙射;

θ′:E(G(k)+2)→[9,q+8]是雙射.

θ′:E(D2,4∪G(k)+2)→[1, q+8]是一一對(duì)應(yīng).

由(1)和(2)可知第一種標(biāo)號(hào)θ就是非連通圖D2,4∪G(k)+2的缺k+1和k+6標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).

令X1=X∪{v1,v3,v6},Y1=Y∪{v2,v4,v5,v7}

所以,第一種標(biāo)號(hào)θ就是非連通圖D2,4∪G(k)+2的特征為k+4,且缺k+1和k+6標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào).

其他各種標(biāo)號(hào)的證明可仿上. 證畢.

以下定理只給出標(biāo)號(hào), 定理證明與定理1的過程類似,故省略.

定理2當(dāng)3≤k+3≤|E(G(k)+3)|)時(shí),非連通圖D2,4∪G(k)+3存在下列優(yōu)美標(biāo)號(hào):

(1) 特征為k+4且缺k+1和k+7標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào).

(2) 特征為k+4且缺k+6和k+8標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào).

非連通圖D2,4∪G(k)+3的各種頂點(diǎn)標(biāo)號(hào)θ定義為

定理3當(dāng)4≤k+4≤|E(G(k)+4)|)時(shí),非連通圖D2,4∪G(k)+4存在下列優(yōu)美標(biāo)號(hào):

(1) 缺k+1和k+3標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(2) 特征為5缺k+1和k+7標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào);

(3) 缺k+5和k+6標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).

非連通圖D2,4∪G(k)+4的各種頂點(diǎn)標(biāo)號(hào)θ定義為

定理4當(dāng)5≤k+5≤|E(G(k)+5)|)時(shí),非連通圖D2,4∪G(k)+5存在下列優(yōu)美標(biāo)號(hào):

(1) 缺k+2和k+8標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(2) 缺k+1和k+3標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).

非連通圖D2,4∪G(k)+5的各種頂點(diǎn)標(biāo)號(hào)θ定義為

定理5當(dāng)6≤k+6≤|E(G(k)+6)|)時(shí),非連通圖D2,4∪G(k)+6存在下列優(yōu)美標(biāo)號(hào):

(1) 缺k+4和k+7標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(2) 缺k+1和k+3標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(3) 缺k+3和k+8標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(4) 缺k+2和k+8標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(5) 缺k+5和k+7標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(6) 缺k+1和k+3標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(7) 缺k+4和k+8標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).

非連通圖D2,4∪G(k)+6的各種頂點(diǎn)標(biāo)號(hào)θ定義為:

定理6當(dāng)7≤k+7≤|E(G(k)+7)|)時(shí),非連通圖D2,4∪G(k)+7存在下列優(yōu)美標(biāo)號(hào):

(1) 缺k+1和k+4標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(2) 缺k+1和k+3標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(3) 缺k+2和k+3標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào);

(4) 缺k+1和k+5標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào).

定義非連通圖D2,4∪G(k)+7的各種頂點(diǎn)標(biāo)號(hào)θ為:

3結(jié)論

本文討論了非連通圖D2,4∪G的優(yōu)美性,給出了非連通圖D2,4∪G是優(yōu)美圖的六個(gè)充分條件.證明了非連通圖D2,4∪G(k)+a(a=2,3,4,5,6,7)都是優(yōu)美的,可為繼續(xù)研究非連通圖Dm,n∪G的優(yōu)美性提供借鑒.

參考文獻(xiàn):

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

(MAKJ.Gracefulgraph[M].Beijing:PekingUniversityPress, 1991:1-247.)

[2] 楊顯文. 關(guān)于C4m蛇的優(yōu)美性[J].工程數(shù)學(xué)學(xué)報(bào), 1995,12(4):108-112.

(YANG X W. OnC4m-snakes' gratefulness[J]. Journal of Engineering Mathematics, 1995,12(4):108-112.)

[3] GALLIAN J A. A dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics, 2013,16:1-308.)

[4] 吳躍生,王廣富,徐保根. 非連通圖C4m∪G的優(yōu)美標(biāo)號(hào)[J]. 重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,32(2):79-83.

(WU Y S, WANG G F, XU B G. The graceful labeling of the unconnected graphC4m∪G[J]. Journal of Chongqing Normal University(Natural Science), 2015,32(2):79-83.)

[5] 吳躍生. 非連通圖G+e∪Hk-1的優(yōu)美性[J].吉首大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,35(2):3-5.

(WU Y S. The graceful labeling of the unconnected graphG+e∪Hk-1[J]. Journal of Jishou University(Natural Science), 2014,35(2):3-5.)

[6] 吳躍生. 非連通圖C4m-1∪G的優(yōu)美標(biāo)號(hào)[J]. 吉首大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,35(3):1-3.

(WU Y S. The graceful labeling of the unconnected graphC4m-1∪G[J]. Journal of Jishou University (Natural Science), 2014,35(3):1-3.

[7] 吳躍生. 再探非連通圖C4m-1∪G的優(yōu)美標(biāo)號(hào)[J]. 吉首大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,36(1):1-4.

(WU Y S. Revisiting the graceful labeling of the unconnected graphC4m-1∪G[J]. Journal of Jishou University(Natural Science), 2015,36(1):1-4.

[8] 吳躍生. 三探非連通圖C4m-1∪G的優(yōu)美標(biāo)號(hào)[J]. 吉首大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,36(4):5-8.

(WU Y S. Further exploration the graceful labeling of the unconnected graphC4m-1∪G[J]. Journal of Jishou University (Natural Science), 2015,36(4):5-8.

[9] 吳躍生.非連通圖D2,6∪G的優(yōu)美標(biāo)號(hào)[J] .海南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,32(1):32-34.

(WU Y S. Graceful labeling of unconnected graphD2,6∪G[J]. Journal of Hainan University (Natural Science ), 2014,32(1):32-34.)

[10] 吳躍生. 非連通圖D2,8∪G的優(yōu)美標(biāo)號(hào)[J]. 西華師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,35(1):4-6.

(WU Y S. The graceful labeling of unconnected graphD2,8∪G[J]. Journal of China West Normal University (Natural Science), 2014,35(1):4-6.)

[11] 吳躍生. 非連通圖C4m-1∪C12m-8∪G的優(yōu)美性[J]. 沈陽大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014,26(4):334-337.

(WU Y S. Graceful labeling of unconnected graphC4m-1∪C12m-8∪G[J]. Journal of Shenyang University (Natural Science), 2014,26(1):334-337.)

[12] 吳躍生. 再探非連通圖C4m-1∪C12m-8∪G的優(yōu)美性[J]. 沈陽大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,27(1):72-76.

(WU Y S. Further discussion on graceful labeling of unconnected graphC4m-1∪C12m-8∪G[J]. Journal of Shenyang University(Natural Science), 2015,27(1):72-76.)

[13] 吳躍生.三探非連通圖C4m-1∪C12m-8∪G的優(yōu)美性[J]. 沈陽大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,27(5):420-425.

(WU Y S. Further Third discussion on graceful labeling of unconnected graphC4m-1∪C12m-8∪G[J]. Journal of Shenyang University (Natural Science), 2015,27(5):420-425.)

[14] 吳躍生. 非連通L5∪G的優(yōu)美標(biāo)號(hào)[J]. 西華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,34(2):30-35.

(WU Y S. The graceful labeling of the unconnected graphL5∪G[J]. Journal of Xihua University (Natural Science), 2015,34(2):30-35.)

【責(zé)任編輯: 肖景魁】

Graceful Labeling of Unconnected GraphD2,4∪G

WuYuesheng

(School of Science, East ChinaJiaotong University, Nanchang 330013, China )

Abstract:The gracefulness of the unconnected graph D2,4∪G is discussed. Six sufficient conditions are given for the gracefulness of unconnected graph D2,4∪G. It proves that the graph D2,4∪G(k)+aare graceful graph for a=2,3,4,5,6,7.

Key words:graceful graph; alternating graph; unconnected graph; graceful labeling

中圖分類號(hào):O 157.5

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):2095-5456(2016)01-0078-04

作者簡介:吳躍生(1959-),男,江西瑞金人,華東交通大學(xué)副教授.

基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(11261019,11361024).

收稿日期:2015-09-08