吳麗鴻 王世英

（1.山西電力職業(yè)技術(shù)學(xué)院 數(shù)學(xué)教研室，山西 太原 030021；2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

幾類圖的優(yōu)美性研究

吳麗鴻1王世英2

（1.山西電力職業(yè)技術(shù)學(xué)院 數(shù)學(xué)教研室，山西 太原 030021；2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

文章討論了連通圖T′n，4、圖T（T′n，4，P m）、圖F n，4、圖T（F n，4，P m）和非連通圖圖C4∪T′n，4的優(yōu)美性，用構(gòu)造的方法給出了這幾類圖的優(yōu)美標(biāo)號，得出這些圖都是優(yōu)美圖.

連通圖；非連通圖；優(yōu)美標(biāo)號；優(yōu)美圖

0 引言

本文討論的圖G（V，E）均為無向簡單圖，其中V（G）和E（G）分別表示圖G（V，E）的頂點(diǎn)集和邊集，｜E（G）｜表示圖G（V，E）的邊數(shù)，未說明的符號及術(shù)語參見文獻(xiàn)［1］.

定義1［2］一個q條邊的簡單圖G（V，E），如果存在一個單射f：V（G）→｛0，1，2，…，q｝，使得對所有的邊e＝（u，v），由f，（e）＝｜f（u）－f（v）｜導(dǎo)出的E（G）→｛1，2，…，q｝是一個雙射，則稱圖G（V，E）是優(yōu)美圖，f是圖G（V，E）的優(yōu)美標(biāo)號（或優(yōu)美值）.

定義2［1］設(shè)u，v是圖G的兩個頂點(diǎn)，若在G中存在一條通路，則稱頂點(diǎn)u，v是連通的.若圖G的每一對不同的頂點(diǎn)都連通，稱圖G是連通的，否則稱為非連通的.

定義3 對于自然數(shù)n，圖C4∪T′n，4表示一個由圖C4和圖T′n，4并起來的連通圖，其中圖C4表示路長為4的一個圈，圖T′n，4表示由n個圈C4順序有一個公共點(diǎn)，其中每個（除兩端點(diǎn)外）圈C4的公共點(diǎn)為相鄰點(diǎn)的圖.

定義4 對于自然數(shù)n，m，圖T（T′n，4，Pm）表示一個由圖T′n，4和Pm（表示有m個頂點(diǎn)的路，記Pm＝v0v1…vm－1）粘結(jié)而成的連通圖.

定義5 對于自然數(shù)n，圖Fn，4表示由n個圈C4順序有一個公共點(diǎn)，其中每個（除兩端點(diǎn)外）圈C4的公共點(diǎn)為不相鄰點(diǎn)的圖.

定義6 對于自然數(shù)n，m，圖T（Fn，4，Pm）表示一個由圖Fn，4和Pm（表示有m個頂點(diǎn)的路，記Pm＝v0v1…vm－1）粘結(jié)而成的連通圖.

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

定理1 對于自然數(shù)n，圖T′n，4是優(yōu)美圖.

證明 設(shè)圖T′n，4頂點(diǎn)及邊如圖1和圖2所示.

當(dāng)n為奇數(shù)時如圖1所示，當(dāng)n為偶數(shù)時如圖2所示.

圖1 T′n，4，其中n為奇數(shù)

圖2 T′n，4，其中n為偶數(shù)

下面給出圖T′n，4的標(biāo)號f（v），

易證得f（v）是圖T′n，4的優(yōu)美標(biāo)號.

定理2 對于自然數(shù)n，非連通圖C4∪T′n，4是優(yōu)美圖.

證明：設(shè)圖C4∪T′n，4頂點(diǎn)及邊如圖3和圖4所示.

當(dāng)n為奇數(shù)時如圖3所示.

圖3 C4∪T′n，4，其中n為奇數(shù)

當(dāng)n為偶數(shù)時如圖4所示.

圖4 C4∪T′n，4，其中n為偶數(shù)

下面給出圖C4∪T′n，4的標(biāo)號f（v），

易證得f（v）是圖C4∪T′n，4的優(yōu)美標(biāo)號.

定理3 對于自然數(shù)n，m，圖T（T′n，4，Pm）是優(yōu)美圖.

證明 設(shè)圖T（T′n，4，Pm）頂點(diǎn)和邊如圖5和圖6所示.

當(dāng)n為偶數(shù)時如圖5所示.

圖5 T（T′n，4，Pm），其中n為偶數(shù)

當(dāng)n為奇數(shù)時如圖6所示.

圖6 T（T′n，4，Pm），其中n為奇數(shù)

設(shè)圖T（T′n，4，Pm）的標(biāo)號f（v）如下：

易證得f（v）是圖T（T′n，4，Pm）的優(yōu)美標(biāo)號.

定理4 對于自然數(shù)n，連通圖Fn，4是優(yōu)美圖.

證明 設(shè)圖Fn，4頂點(diǎn)和邊如圖7所示.

設(shè)圖Fn，4的標(biāo)號f（v）如下：

易證得f（v）是圖Fn，4的優(yōu)美標(biāo)號.

定理5 對于自然數(shù)n，連通圖T（Fn，4，Pm）是優(yōu)美圖.

設(shè)圖T（Fn，4，Pm）頂點(diǎn)和邊如圖8所示.

圖7 Fn，4

圖8 T（Fn，4，Pm）

設(shè)圖T（Fn，4，Pm）的標(biāo)號f（v）如下：

［1］Bondy J A，Murty U S R.Graph theory with applications［M］.New York：Macmillan London and Elsevier，1976

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

［3］楊顯文，于敬蓮.關(guān)于圖C4∪Fm，4的優(yōu)美性［J］.吉林廣播電視大學(xué)學(xué)報，2002，58（2）：54-56

［4］林育青.關(guān)于圖P3n的優(yōu)美性［J］.華南師范大學(xué)學(xué)報（自然科學(xué)版），2000（3）：21-24

［5］嚴(yán)謙泰，李武裝.關(guān)于圖P3n優(yōu)美性的研究［J］.數(shù)學(xué)的實(shí)踐和認(rèn)識，2005，35（4）：131-139

［6］王天成.一類鏈圖的優(yōu)美性研究［J］.電腦知識與技術(shù)，2010，6（19）：80-82

On the Gracefulness Study of Several Classes of Graphs

Wu Lihong1Wang Shiying2
（1.Department of Mathematics，Shanxi Electric Vocational and Technical College，Taiyuan 030021；2.School of Mathematical Sciences，Shanxi University，Taiyuan 030006，China）

We discussed the gracefulness of union graph ofT′n，4，T（T′n，4，Pm），F(xiàn)n，4，T（Fn，4，Pm）and disjoint union graph ofC4∪Tn，4，We give the graceful labelings of these graph and prove them be graceful graphs.

joint union graph；disjoint union graph；graceful labelings；graceful guaphs

王映苗】

1672-2027（2011）03-0050-04

O157.5

A

2011-03-02

吳麗鴻（1976-），女，山西萬榮人，碩士，山西電力職業(yè)技術(shù)學(xué)院助教，主要從事圖論及其應(yīng)用研究.