非连通图D3，4∪G的优美标号

吴跃生

(华东交通大学 理学院，南昌 330013)

非连通图D3，4∪G的优美标号

吴跃生

(华东交通大学 理学院，南昌 330013)

讨论了非连通图D3，4∪G的优美性，给出了非连通图D3，4∪G是优美图的几个充分条件。

优美图；交错图；非连通图；优美标号

1 引言与概念

记号V(G)和E(G)分别表示图G的顶点集和边集，m和n均为非负整数，且满足0≤m

图的优美标号问题是组合数学中一个热门课题[1-14]。

定义1[1]对于一个图G=(V，E)，称G是优美图，θ为G的一组优美标号是指：如果存在一个单射θ：V(G)→[0，|E(G)|]使得对所有边e=uv∈E(G)，由θ′(e)=|θ(u)-θ(v)|导出的E(G)→[1，|E(G)|]是一个双射。

把任意m个圈Cn的恰有一个公共点所组成的图记作Dm，n[1]。

文[13]和[14]分别研究了非流通图D2，6∪G和非流通图D2，8∪G的优美标号。

D3，4存在特征为3，且缺6，8和11标号值的交错标号，如图1所示。为方便起见，把如图1所示的标号记为：(1；0，12，10；9，2，7；5，3，4)

图1 图D3，4的交错标号

本文将讨论非连通图D3，4∪G的优美性。

2 主要结论及其证明

定理1 当2≤k+2≤|E(Gk+2)|时，非连通图D3，4∪Gk+2存在特征为k+5，且缺k+1，k+8和k+10标号值的交错标号。

图2 图D3，4

定义D3，4∪Gk+2的顶点标号θ为：

下面证明θ是非连通图D3，4∪Gk+2的优美标号。

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

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

容易验证：θ：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]是一一对应的。

由(1)和(2)可知θ就是非连通图D3，4∪Gk+2的缺k+1，k+8和k+10标号值的优美标号。

所以，θ就是非连通图D3，4∪Gk+2的特征，为k+5，且缺k+1，k+8和k+10标号值的交错标号。证毕。

下面的定理只给出标号，证明过程可仿定理1。

定理2 当2≤k+2≤|E(Gk+2)|时，非连通图D3，4∪Gk+2存在特征为k+4，且缺k+7，k+10和k+12标号值的交错标号。

定义D3，4∪Gk+2的顶点标号θ为：

定理3 当3≤k+3≤|E(Gk+3)|时，非连通图D3，4∪Gk+3存在特征为k+5，且缺k+1，k+8和k+11标号值的交错标号。

定义D3，4∪Gk+3的顶点标号θ为：

定理4 当10≤k+10≤|E(Gk+10)|时，非连通图D3，4∪Gk+10存在缺k+6，k+8和k+11标号值的优美标号。

定义D3，4∪Gk+10的顶点标号θ为：

定理5 当10≤k+10≤|E(Gk+10)|时，非连通图D3，4∪Gk+10存在缺k+3，k+5和k+12标号值的优美标号。

定义D3，4∪Gk+10的顶点标号θ为：

定理6 当11≤k+11≤|E(Gk+11)|时，非连通图D3，4∪Gk+11存在缺k+1，k+4和k+6标号值的优美标号。

定义D3，4∪Gk+11的顶点标号θ为：

定理7 当10≤k+10≤|E(Gk+10)|时，非连通图D3，4∪Gk+10存在缺k+1，k+3和k+6标号值的优美标号。

定义D3，4∪Gk+10的顶点标号θ为：

定理8 当9≤k+9≤|E(Gk+9)|时，非连通图D3，4∪Gk+9存在缺k+2，k+5和k+12标号值的优美标号。

定义D3，4∪Gk+9的顶点标号θ为：

定理9 当2≤k+2≤|E(Gk+2)|时，非连通图D3，4∪Gk+2存在缺k+2，k+5和k+12标号值的优美标号。

定义D3，4∪Gk+2的顶点标号θ为：

定理10 当11≤k+11≤|E(Gk+11)|时，非连通图D3，4∪Gk+11存在缺k+1，k+5和k+9标号值的优美标号。

定义D3，4∪Gk+11的顶点标号θ为：

定理11 当10≤k+10≤|E(Gk+10)|时，非连通图D3，4∪Gk+10存在缺k+4，k+8和k+12标号值的优美标号。

定义D3，4∪Gk+10的顶点标号θ为：

定理12 当4≤k+4≤|E(Gk+4)|时，非连通图D3，4∪Gk+4存在缺k+2，k+6和k+9标号值的优美标号。

定义D3，4∪Gk+4的顶点标号θ为：

引理1[1]对任意正整数n，设C4n是有4n个顶点的圈，则C4n存在特征为2n-1，且缺3n的交错标号。

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

推论1 非连通图D3，4∪C4存在特征为6，且缺2，9和11标号值的交错标号。

非连通图的存在特征为6，且缺2，9和11标号值的交错标号为：

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标号值的交错标号。

非连通图D3，4∪C4的特征为5，且缺8，11和13标号值的交错标号为

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标号值的交错标号。

非连通图D3，4∪C8的特征为8，且缺4，11和14标号值的交错标号为：

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标号值的优美标号。

非连通图D3，4∪C36的缺23，25和28标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C36的缺20，22和29标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C40的缺20，23和25标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C36的缺18，20和23标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C32的缺17，20和27标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C4的缺4，8和12标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C40的缺20，24和28标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C36的缺21，25和29标号值的优美标号为：

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标号值的优美标号。

非连通图D3，4∪C36的缺7，11和14标号值的优美标号为：

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标号值的交错标号，6=3+3，连续应用定理3，有如下的推理。

推论13 非连通图nD3，4是交错图。

例 非连通图3D3，4的特征为13交错标号为：

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] 马克杰.优美图[M].北京：北京大学出版社，1991：1-2.

[2] 杨显文.关于C4m蛇的优美性[J].工程数学学报，1995，12(4)：108-112.

[3] 吴跃生，王广富，徐保根.非连通图C4m∪G的优美标号[J].重庆师范大学学报：自然科学版，2015，32(2)：79-83.

[5] 吴跃生，王广富，徐保根.关于C4h+1⊙K1的(Gr1，Gr2，…，Gr4h+1，Gr4h+2)-冠的优美性[J].山东大学学报：理学版，2013，48(4)：25-27.

[6] 吴跃生.关于圈C4h+3的(Gr1，Gr2，…，Gr4h+3)-冠的优美性[J].吉首大学学报：自然科学版，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的优美性[J].吉首大学学报：自然科学版，2014，35(2)：3-5.

[9] 吴跃生.非连通图2C4(3m-1)∪C8m-1∪G的优美标号[J].唐山学院学报，2014，27(3)：12-14.

[10] 吴跃生.再探非连通图2C4(3m-1)∪C8m-1∪G的优美标号[J].唐山学院学报，2014，27(6)：1-4.

[11] 吴跃生非连通图2C4m∪G是优美图的五个充分条件[J].唐山学院学报，2015，28(3)：4-7.

[12] 吴跃生.三探非连通图C4m-1∪G的优美标号[J].吉首大学学报：自然科学版，2015，36(4)：5-8.

[13] 吴跃生.非连通图D2，6∪G的优美标号[J].海南大学学报：自然科学版，2014：32(1)：32-34.

[14] 吴跃生.非连通图D2，8∪G的优美标号[J].西华师范大学学报：自然科学版，2014：35(1)：4-6.

(责任编校：夏玉玲)

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