圖(s〈C4，3〉)∪Pm的優美性

吳 躍 生

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

?

圖(s〈C4，3〉)∪Pm的優美性

吳 躍 生

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

[摘要]研究了圖(s〈C4，3〉)∪Pspan的優美性，證明了當s為大于等于2的自然數，m為任意正整數時，圖(s〈C4，3〉)∪Pspan是優美的.其中圖〈C4，3〉是將3個C4中每個C4的一個頂點粘接到一起得到的新圖，Pspan是有m+1個頂點的路，而(s〈C4，3〉)∪Pspan是s個〈C4，3〉與一個Pspan的非連通并.文中所得結果部分解決了已有文獻給出的猜想.

[關鍵詞]優美圖；交錯圖；非連通圖；路

1預備知識

優美圖因其應用性和趣味性，引起眾多學者的廣泛研究.[1-10]文獻[7-8]研究了圖(s〈C4，n〉)∪Pm的優美性，文獻[7]中還給出了如下猜想：?m，n，?s≥2，圖(s〈C4，n〉)∪Pm是優美的.本文證明了當n=3時，此猜想成立.

定義1[1]對于一個圖G=(V，E)，若存在一個單射

使得對所有邊e=uv∈E(G)，由

定義2[2]設θ是圖G的優美標號，

V(G)=X∪Y，X∩Y=?.

如果

則稱θ是G的交錯標號，稱G是在交錯標號θ下的交錯圖，稱k為交錯圖G關于交錯標號θ的特征.

定義3[7-8]指定圖C4的一個頂點為根，將n個C4的根粘在一起得到的圖記為〈C4，n〉，粘結點記為b，則稱〈C4，n〉中的每個C4為分支.Pm是有m+1個頂點的簡單通路，圖(s〈C4，n〉)∪Pm是s個〈C4，n〉與一個Pm的非連通并.

2主要結果及其證明

引理1[5]設路Pm=v0v1v2…vm.?a∈{0，1，2，…，m}，路Pm存在一個優美標號θ，使得θ(v0)=a.

V(Gi)=(Xi，Yi)，

引理3[8]當n>2時，非連通圖2〈C4，n〉存在特征為4n，缺4n+2和8n-1標號值的交錯標號.

引理4[11]當T為優美樹時，設T⊙K1是優美樹T中優美值為1的頂點粘接一條懸掛邊后所形成的樹，則非連通圖Gk+2∪T⊙K1是優美圖；當T為交錯樹時，設T的交錯標號θ1的特征為k1，(X1，Y1) 是T的二分劃，

則非連通圖Gk+2∪T⊙K1是交錯圖.

引理5非連通圖3〈C4，3〉存在特征為18，缺20和35標號值的交錯標號.

證明如圖1所示，非連通圖3〈C4，3〉存在特征為18，缺20和35標號值的交錯標號.

定理1當s≥2為自然數，m為任意正整數時，非連通圖(s〈C4，3〉)∪Pm是優美的.

證明由引理1—引理5即可推出本定理結論.

例1非連通圖(3〈C4，3〉)∪P3的交錯標號如圖2所示.非連通圖(3〈C4，3〉)∪P5的優美標號如圖3所示.

引理6(ⅰ) 如果T為優美樹，且T⊙K1是優美樹T中優美值為2的頂點粘接一條懸掛邊后所形成的樹，則非連通圖Gk+3∪T⊙K1是優美圖；

(ⅱ) 如果T為交錯樹，設T的交錯標號θ1的特征為k1，(X1，Y1)是T的二分劃，

則非連通圖Gk+3∪T⊙K1是交錯圖.

證明(ⅰ) 設樹T的優美標號為θ1，θ1(v1)=2.在v1處粘接的一條懸掛邊為v1v2，頂點v2為懸掛點(或葉)，

定義非連通圖Gk+3∪T⊙K1的標號θ2如下：

下面證明θ2是非連通圖Gk+3∪T⊙K1的優美標號.

(1) 映射

θ2:V(Gk+3)→[0，k]∪[k+4+m，m+n]∪{k+1+m，k+2+m}

是單射，映射

θ2:V(T⊙K1)→[k+1，k+m]∪{k+m+3}

也是單射，所以映射

θ2:V(Gk+3∪T⊙K1)→[0，n+m]

是單射.

(2) 映射

是雙射.

由優美標號的定義可知θ2是非連通圖G∪T⊙K1的優美標號.

(ⅱ) 當T為交錯樹時，令

X2=X1∪X，

Y2=Y1∪Y∪{v2}，

則由已知條件有

即θ2是非連通圖G∪T⊙K1的交錯標號，此交錯標號的特征為k1+1+k.證畢.

引理7圖〈C4，3〉存在特征為3，缺6標號值的交錯標號.

證明圖4為〈C4，3〉的交錯標號，由圖4可知引理結論正確.

圖4　圖〈C4，3〉的交錯標號

定理2當m為大于等于2的自然數時，〈C4，3〉∪Pm是優美的.

證明由引理1，引理6和引理7即可推出本定理結論.

例2非連通圖〈C4，3〉∪P4的交錯標號如圖5所示.非連通圖〈C4，3〉∪P6的優美標號如圖6所示.

圖5　圖〈C4，3〉∪P4的交錯標號

圖6　圖〈C4，3〉∪P6的優美標號

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

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

[3]吳躍生.非連通圖C4m-1∪G的優美標號[J].吉首大學學報(自然科學版)，2014，35(3):1-3.

[4]吳躍生.再探非連通圖C4m-1∪G的優美標號[J].吉首大學學報(自然科學版)，2015，36(1):1-4.

[5]FLANDRIN E，FOURNIER I，CERMA A.Numotations gracieuses des chemins[J].Ars Combin，1983，16:149-181.

[7]張志尚，張慶成，王春月.關于(s〈C4，n〉)∪Pm的優美性[J].東北師大學報(自然科學版)，2011，43(3)：14-18.

[8]杜萬根.關于(s〈C4，n〉)∪Pm的優美性[J].蘇州大學學報(自然科學版)，2012，28(2):7-11.

[9]FRUCHTRW，SAUNASLC.Gracefulnumheringofsnakeswithconstantsonthefirst1abe1[J].ArsCombin，1985，20：143-157.

[10]GALLIAN J A. A dynamic survey of graph labeling[J/OL].The Electronic Journal of Combinatorics，2014[2014-05-23].http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.

[11]吳躍生，王廣富，徐保根.非連通圖G∪T⊙K1的優美性[J].東北師大學報(自然科學版)，2014，46(1)：14-16.

(責任編輯：李亞軍)

On the gracefulness of (s〈C4，3〉)∪Pm

WU Yue-sheng

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

Abstract:This article deals with the gracefulness of graph (s〈C4，3〉)∪Pspanand proves that (s〈C4，3〉)∪Pspanis graceful when s≥2(s and m are positive integer)，where the graph 〈C4，3〉 is achieved by identifying a vertex of each C4 of 3C4s with one vertex，graph Pspanis the path with m+1 vertexes，and graph (s〈C4，3〉)∪Pspanis the disjoint union of (s〈C4，3〉)s and Pspan.

Keywords:graceful graph；alternating graph；unconnected graph；path

[中圖分類號]O 157.5[學科代碼]110·7470

[文獻標志碼]A

[作者簡介]吳躍生(1959—)，男，碩士，副教授，主要從事圖論研究.

[基金項目]國家自然科學基金資助項目(11261019，11361024).

[收稿日期]2014-05-23

[文章編號]1000-1832(2016)01-0018-04

[DOI]10.16163/j.cnki.22-1123/n.2016.01.005