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

吳躍生

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

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

吳躍生

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

討論了非連通圖D3，4∪G的優(yōu)美性，給出了非連通圖D3，4∪G是優(yōu)美圖的幾個(gè)充分條件。

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

1 引言與概念

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

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

定義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]。

文[13]和[14]分別研究了非流通圖D2，6∪G和非流通圖D2，8∪G的優(yōu)美標(biāo)號(hào)。

D3，4存在特征為3，且缺6，8和11標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)，如圖1所示。為方便起見(jiàn)，把如圖1所示的標(biāo)號(hào)記為：(1；0，12，10；9，2，7；5，3，4)

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

本文將討論非連通圖D3，4∪G的優(yōu)美性。

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

定理1 當(dāng)2≤k+2≤|E(Gk+2)|時(shí)，非連通圖D3，4∪Gk+2存在特征為k+5，且缺k+1，k+8和k+10標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

圖2 圖D3，4

定義D3，4∪Gk+2的頂點(diǎn)標(biāo)號(hào)θ為：

下面證明θ是非連通圖D3，4∪Gk+2的優(yōu)美標(biāo)號(hào)。

(1)θ：X→[0，k]是單射(或雙射)；θ：Y→[k+13，q+12]-{k+14}是單射；

θ：V(D3，4)→[k+2，k+12]∪{k+14}-{k+8，k+10}是雙射；

容易驗(yàn)證：θ：V(D3，4∪Gk+2)→[0，q+12]-{k+8，k+10}是單射。

(2)θ′(v1v2)=|θ(v1)-θ(v2)|=12，θ′(v2v3)=11，θ′(v4v3)=9，θ′(v4v1)=10，θ′(v5v3)=8，θ′(v6v5)=7，θ′(v6v7)=5，θ′(v7v3)=6，θ′(v8v3)=4，θ′(v8v9)=2，θ′(v10v9)=1，θ′(v10v3)=3。

θ′：E(D3，4)→[1，12]是雙射；

θ′：E(Gk+2)→[13，q+12]是雙射。

θ′：E(D3，4∪Gk+2)→[1，q+12]是一一對(duì)應(yīng)的。

由(1)和(2)可知θ就是非連通圖D3，4∪Gk+2的缺k+1，k+8和k+10標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

所以，θ就是非連通圖D3，4∪Gk+2的特征，為k+5，且缺k+1，k+8和k+10標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。證畢。

下面的定理只給出標(biāo)號(hào)，證明過(guò)程可仿定理1。

定理2 當(dāng)2≤k+2≤|E(Gk+2)|時(shí)，非連通圖D3，4∪Gk+2存在特征為k+4，且缺k+7，k+10和k+12標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

定義D3，4∪Gk+2的頂點(diǎn)標(biāo)號(hào)θ為：

定理3 當(dāng)3≤k+3≤|E(Gk+3)|時(shí)，非連通圖D3，4∪Gk+3存在特征為k+5，且缺k+1，k+8和k+11標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

定義D3，4∪Gk+3的頂點(diǎn)標(biāo)號(hào)θ為：

定理4 當(dāng)10≤k+10≤|E(Gk+10)|時(shí)，非連通圖D3，4∪Gk+10存在缺k+6，k+8和k+11標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+10的頂點(diǎn)標(biāo)號(hào)θ為：

定理5 當(dāng)10≤k+10≤|E(Gk+10)|時(shí)，非連通圖D3，4∪Gk+10存在缺k+3，k+5和k+12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+10的頂點(diǎn)標(biāo)號(hào)θ為：

定理6 當(dāng)11≤k+11≤|E(Gk+11)|時(shí)，非連通圖D3，4∪Gk+11存在缺k+1，k+4和k+6標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+11的頂點(diǎn)標(biāo)號(hào)θ為：

定理7 當(dāng)10≤k+10≤|E(Gk+10)|時(shí)，非連通圖D3，4∪Gk+10存在缺k+1，k+3和k+6標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+10的頂點(diǎn)標(biāo)號(hào)θ為：

定理8 當(dāng)9≤k+9≤|E(Gk+9)|時(shí)，非連通圖D3，4∪Gk+9存在缺k+2，k+5和k+12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+9的頂點(diǎn)標(biāo)號(hào)θ為：

定理9 當(dāng)2≤k+2≤|E(Gk+2)|時(shí)，非連通圖D3，4∪Gk+2存在缺k+2，k+5和k+12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+2的頂點(diǎn)標(biāo)號(hào)θ為：

定理10 當(dāng)11≤k+11≤|E(Gk+11)|時(shí)，非連通圖D3，4∪Gk+11存在缺k+1，k+5和k+9標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+11的頂點(diǎn)標(biāo)號(hào)θ為：

定理11 當(dāng)10≤k+10≤|E(Gk+10)|時(shí)，非連通圖D3，4∪Gk+10存在缺k+4，k+8和k+12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+10的頂點(diǎn)標(biāo)號(hào)θ為：

定理12 當(dāng)4≤k+4≤|E(Gk+4)|時(shí)，非連通圖D3，4∪Gk+4存在缺k+2，k+6和k+9標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義D3，4∪Gk+4的頂點(diǎn)標(biāo)號(hào)θ為：

引理1[1]對(duì)任意正整數(shù)n，設(shè)C4n是有4n個(gè)頂點(diǎn)的圈，則C4n存在特征為2n-1，且缺3n的交錯(cuò)標(biāo)號(hào)。

注意到：3n=(2n-1)+n+1，由定理1和引理1有如下的推理。

推論1 非連通圖D3，4∪C4存在特征為6，且缺2，9和11標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

非連通圖的存在特征為6，且缺2，9和11標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)為：

D3，4：(4；3，15，13；12，5，10；8，6，7)；C4：0，16，1，14。

由定理2和引理1有如下的推理。

推論2 非連通圖D3，4∪C4存在特征為5，且缺8，11和13標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

非連通圖D3，4∪C4的特征為5，且缺8，11和13標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)為

D3，4：(3；2，12，10；15，4，9；7，5，6)；C4：0，16，1，14。

由定理3和引理1有如下的推理。

推論3 非連通圖D3，4∪C8存在特征為8，且缺4，11和14標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

非連通圖D3，4∪C8的特征為8，且缺4，11和14標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)為：

D3，4：(6；5，15，13；18，7，12；10，8，9)；C8：0，20，1，19，2，17，3，16。

由定理4和引理1有如下的推理。

推論4 非連通圖D3，4∪C36存在缺23，25和28標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C36的缺23，25和28標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(18；39，29，27；26，19，24；22，20，21)；

C36：0，48，1，47，2，46，3，45，4，44，5，43，6，42，7，41，8，40，9，38，10，37，11，36，12，35，13，34，14，33，15，32，16，31，17，30。

由定理5和引理1有如下的推理。

推論5 非連通圖D3，4∪C36存在缺20，22和29標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C36的缺20，22和29標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(27；28，18，39；19，26，21；23，25，24)；

C36：0，48，1，47，2，46，3，45，4，44，5，43，6，42，7，41，8，40，9，38，10，37，11，36，12，35，13，34，14，33，15，32，16，31，17，30。

由定理6和引理1有如下的推理。

推論6 非連通圖D3，4∪C40存在缺20，23和25標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C40的缺20，23和25標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(30；31，21，42；22，29，24；26，28，27)；

C40：0，52，1，51，2，50，3，49，4，48，5，47，6，46，7，45，8，44，9，43，10，41，11，40，12，39，13，38，14，37，15，36，16，35，17，34，18，33，19，32。

由定理7和引理1有如下的推理。

推論7 非連通圖D3，4∪C36存在缺18，20和23標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C36的缺18，20和23標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(28；29，19，21；39，27，22；24，26，25)；

C36：0，48，1，47，2，46，3，45，4，44，5，43，6，42，7，41，8，40，9，38，10，37，11，36，12，35，13，34，14，33，15，32，16，31，17，30。

由定理8和引理1有如下的推理。

推論8 非連通圖D3，4∪C32存在缺17，20和27標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C32的缺17，20和27標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(25；26，16，18；36，24，19；21，23，22)；

C32：0，44，1，43，2，42，3，41，4，40，5，39，6，38，7，37，8，35，9，34，10，33，11，32，12，31，13，30，14，29，15，28。

由定理9和引理1有如下的推理。

推論9 非連通圖D3，4∪C4存在缺4，8和12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C4的缺4，8和12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(15；10，5，3；7，6，9；11，2，13)；C4：0，16，1，14。

由定理10和引理1有如下的推理。

推論10 非連通圖D3，4∪C40存在缺20，24和28標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C40的缺20，24和28標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(31；22，27，29；25，26，23；21，30，42)；

C40：0，52，1，51，2，50，3，49，4，48，5，47，6，46，7，45，8，44，9，43，10，41，11，40，12，39，13，38，14，37，15，36，16，35，17，34，18，33，19，32。

由定理11和引理1有如下的推理。

推論11 非連通圖D3，4∪C36存在缺21，25和29標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C36的缺21，25和29標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(28；19，24，26；22，23，20；18，27，39)；

C36：0，48，1，47，2，46，3，45，4，44，5，43，6，42，7，41，8，40，9，38，10，37，11，36，12，35，13，34，14，33，15，32，16，31，17，30。

推論12 非連通圖D3，4∪C12存在缺7，11和14標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

非連通圖D3，4∪C36的缺7，11和14標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)為：

D3，4：(17；9，21，15；12，13，10；8，16，6)；

C12：0，24，1，23，2，22，3，20，4，19，5，18。

注意到：定理1、定理3中k+8=(k+5)+3，定理2中k+7=(k+4)+3，又D3，4存在特征為3，且缺6，8和11標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)，6=3+3，連續(xù)應(yīng)用定理3，有如下的推理。

推論13 非連通圖nD3，4是交錯(cuò)圖。

例 非連通圖3D3，4的特征為13交錯(cuò)標(biāo)號(hào)為：

D3，4：(1；0，36，34；33，2，31；29，3，28)；

D3，4：(6；5，27，25；30，7，24；22，8，21)；

D3，4：(11；10，20，18；23，12，17；15，13，14)。

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

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

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

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

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

[7] Gallian J.A.A dynamic survey of graph labeling[J].The Electronic Joumal of Combinatorics，2013，16(DS6)：1-308.

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

[9] 吳躍生.非連通圖2C4(3m-1)∪C8m-1∪G的優(yōu)美標(biāo)號(hào)[J].唐山學(xué)院學(xué)報(bào)，2014，27(3)：12-14.

[10] 吳躍生.再探非連通圖2C4(3m-1)∪C8m-1∪G的優(yōu)美標(biāo)號(hào)[J].唐山學(xué)院學(xué)報(bào)，2014，27(6)：1-4.

[11] 吳躍生非連通圖2C4m∪G是優(yōu)美圖的五個(gè)充分條件[J].唐山學(xué)院學(xué)報(bào)，2015，28(3)：4-7.

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

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

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

(責(zé)任編校：夏玉玲)

The Graceful Labeling of the Unconnected GraphD3，4∪G

WU Yue-sheng

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

The author of this paper discusses the gracefulness of the unconnected graphD3，4∪Gand put forward some sufficient conditions for the gracefulness of the unconnected graph.

graceful graph；interlaced image； unconnected graph； graceful labeling

O157.5

A

1672-349X(2015)05-0003-04

10.16160/j.cnki.tsxyxb.2015.06.002