一類鏈圖的優美性

吳麗鴻，王世英

(1.山西電力職業技術學院基礎部，太原 030021;2.山西大學數學科學學院，太原 030006)

1 定義

優美圖是圖論中的重要課題，但至今由于缺乏一般性的研究手段，尋找具有優美性的圖類仍是這個領域內目前的研究重點。本文討論的圖G(V，E)均為無向簡單圖，其中V(G)和E(G)分別表示圖G(V，E)的頂點集和邊集，|E(G)|表示圖G(V，E)的邊數，未說明的符號及術語見參考文獻[1]。

定義1[1]若一個圖的頂點集可以分解為兩個(非空)子集X和Y，使得每條邊都有一個端點在X中，另一個端點在Y中，這樣的一個圖稱為二部圖(或偶圖);這樣的一種分類(X，Y)稱為二分類;若X的每個頂點都和Y中的每個頂點相連，稱為一個完全二部圖;若|X|=m，而|X|=n，這樣的完全二部圖記為 Km，n.

定義2[2]一個q條邊的簡單圖G(V，E)，如果存在一個單射 f∶V(G)→ {0，1，2，…，q}，使得對所有的e=(u，v)，由f'(e)=|f(u)－f(v)|導出的E(G)→ {1，2，…，q}是一個雙射，則稱圖 G(V，E)是優美圖，f是圖G(V，E)的優美標號(或優美值)。

定義3 設k個完全二部圖k2，mi，對應的二分類為(Xi，Yi)，且 |Xi|=2，|Yi|=mi，其中mi為大于1 的正整數，i=1，2，…，k.將 Yi中的兩個點分別定義為前點和后點。將Xi中兩個點分別定義為起點和終點。

定義4 由 k 個完全二部圖 K2，m1，K2，m2，…，K2，mk的前點和后點依次粘接而成的圖稱為鏈圖T1.

定義5 由 k 個完全二部圖 K2，m1，K2，m2，…，K2，mk的起點和終點依次粘接而成的圖稱為鏈圖T2.

定義6 由鏈圖T1中Yk的后點與長為n的路Pn的一個端點粘接得到的圖稱為鏈圖T3.

定義7 由鏈圖T2中Yk的終點與長為n的路Pn的一個端點粘接得到的圖稱為鏈圖T4.

定義8 設 k 個完全二部圖 K2，m1，K2，m2，…，K2，mk，將 K2，mi的終點和 K2，mi+1的前點粘接得到的圖記為其中 i=1，3，5，…，k － 1，將，的起點和后點依次粘接而成的圖稱為鏈圖T5.

定理 1[3]對于自然數 n，連通圖 T(Fn，4，Pm)是優美圖。

定理2[3]對于自然數n，連通圖Fn，4是優美圖。本文將文獻[3]的定理4和定理5的條件范圍加以擴大，得到了一些優美圖。文獻[3]-文獻[11]均對一些圖進行了優美性研究。

2 主要結果及其證明

定理3 對于大于1的正整數 k，m1，m2，…，mk，圖T1是優美圖。

證明 設圖T1頂點和邊如圖1所示。

下面給出圖T1的標號f(v):

設m=m1+ … +mk，

f(U0)=0，

f(Ui)=m1+ … +mi+i，(i=1，2，…，k －1)，

f(Vi)=2m － i+1，(i=1，2，…，m － k+1)，

f(Wi)=m1+ … +mi+i－1，(i=1，2，…，k).

易證得f(v)是圖T1的優美標號。

圖1 鏈圖T1Fig.1 Chain graph T1

定理4 對于大于1的正整數 k，m1，m2，…，mk，圖T2是優美圖。

證明 設圖T2的頂點和邊如圖2所示。

下面給出圖T2的標號f(v):

設m=m1+ … +mk，

f(V0)=0，

f(Ui)=2m+1 － i，(i=1，2，…，m)，

f(Vi)=m1+ … +mi，(i=1，2，…，k).

易證得f(v)是圖T2的優美標號。

圖2 鏈圖T2Fig.2 Chain graph T2

定理5 對于大于1的正整數 k，m1，m2，…，mk，正整數n，圖T3是優美圖。

證明 設圖T3的頂點和邊如圖3(n為偶數)和圖4(n為奇數)所示。

下面給出圖T3的標號f(v):

設m=m1+… +mk，

f(U0)=0，

f(Ui)=m1+ … +mi+i，(i=1，2，…，k －1)，

f(Vi)=2m+n － i+1，(i=1，2，…，m － k+1)，

f(Wi)=m1+ … +mi+i－1，(i=1，2，…，k).

當n為偶數時，

當n為奇數時，

易證得f(v)是圖T3的優美標號。

圖3 鏈圖T3，n為偶數Fig.3 Chain graph T3

圖4 鏈圖T3，n為奇數Fig.4 Chain graph T3

定理6 對于大于1的正整數 k，m1，m2，…，mk，正整數n，圖T4是優美圖。

證明 設圖T4的頂點和邊如圖5(n為偶數)和圖6(n為奇數)所示。

下面給出圖T4的標號f(v):

設m=m1+… +mk，

f(Ui)=2m+n+1 － i，(i=1，2，…，m)，

f(V0)=0，

f(Vi)=m1+ … +mi，(i=1，2，…，k).

當n為偶數時，

當n為奇數時，

易證得f(v)是圖T4的優美標號。

圖5 鏈圖T4，n為偶數Fig.5 Chain graph T4

圖6 鏈圖T4，n為奇數Fig.6 Chain graph T4

定理7 對于大于1的正整數k，m1，m2，…，mk和正整數n，圖T5是優美圖。

證明 設圖T5的頂點和邊如圖7所示。

下面給出圖T5的標號f(v):

設m=m1+… +mk，

易證得f(v)是圖T5的優美標號。

圖7 鏈圖T5Fig.7 Chain graph T5

證明了這幾類圖是優美圖，可以猜想將這幾類圖分別首尾相接而得到的圖的優美性。

[1]BONDY J A，MURTY U S R.Graph Theory with Applications[M].New York:Macmillan London and Elsevier，1976.

[2]馬杰克.優美圖[M].北京:北京大學出版社，1991.

[3]吳麗鴻，王世英.幾類圖的優美性研究[J].太原師范學院學報:自然科學版，2011，10(3):50-53.

[4]楊顯文，于敬蓮.關于圖 C4∪Fm，4的優美性[J].吉林廣播電視大學學報，2002，58(2):54-56.

[7]王天成.一類鏈圖的優美性研究[J].電腦知識與技術，2010，6(19):80-82.

[8]曾一平.等長輻射樹Tnm的優美性[J].太原重型機械學院學報，1988，9(1):9-16.

[9]王衛兵，楊徐昕.一類偶階圖的邊優美性[J].數學理論與應用，2010，30(2):81-84.

[10]吳躍生，徐保根.關于圖的優美性[J].安徽大學學報，2011，35(5):14-17.

[11]李武裝，苗宗文，嚴謙泰.幾類有趣圖的奇優美性和奇強協調性[J].數學的實踐與認識，2011，41(4):234-239.