一類鏈圖的優(yōu)美性

吳麗鴻，王世英

(1.山西電力職業(yè)技術(shù)學(xué)院基礎(chǔ)部，太原 030021;2.山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院，太原 030006)

1 定義

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

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

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

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

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

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

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

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

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

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

定理2[3]對于自然數(shù)n，連通圖Fn，4是優(yōu)美圖。本文將文獻(xiàn)[3]的定理4和定理5的條件范圍加以擴(kuò)大，得到了一些優(yōu)美圖。文獻(xiàn)[3]-文獻(xiàn)[11]均對一些圖進(jìn)行了優(yōu)美性研究。

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

定理3 對于大于1的正整數(shù) k，m1，m2，…，mk，圖T1是優(yōu)美圖。

證明 設(shè)圖T1頂點(diǎn)和邊如圖1所示。

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

設(shè)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的優(yōu)美標(biāo)號。

圖1 鏈圖T1Fig.1 Chain graph T1

定理4 對于大于1的正整數(shù) k，m1，m2，…，mk，圖T2是優(yōu)美圖。

證明 設(shè)圖T2的頂點(diǎn)和邊如圖2所示。

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

設(shè)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的優(yōu)美標(biāo)號。

圖2 鏈圖T2Fig.2 Chain graph T2

定理5 對于大于1的正整數(shù) k，m1，m2，…，mk，正整數(shù)n，圖T3是優(yōu)美圖。

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

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

設(shè)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).

當(dāng)n為偶數(shù)時(shí)，

當(dāng)n為奇數(shù)時(shí)，

易證得f(v)是圖T3的優(yōu)美標(biāo)號。

圖3 鏈圖T3，n為偶數(shù)Fig.3 Chain graph T3

圖4 鏈圖T3，n為奇數(shù)Fig.4 Chain graph T3

定理6 對于大于1的正整數(shù) k，m1，m2，…，mk，正整數(shù)n，圖T4是優(yōu)美圖。

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

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

設(shè)m=m1+… +mk，

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

f(V0)=0，

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

當(dāng)n為偶數(shù)時(shí)，

當(dāng)n為奇數(shù)時(shí)，

易證得f(v)是圖T4的優(yōu)美標(biāo)號。

圖5 鏈圖T4，n為偶數(shù)Fig.5 Chain graph T4

圖6 鏈圖T4，n為奇數(shù)Fig.6 Chain graph T4

定理7 對于大于1的正整數(shù)k，m1，m2，…，mk和正整數(shù)n，圖T5是優(yōu)美圖。

證明 設(shè)圖T5的頂點(diǎn)和邊如圖7所示。

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

設(shè)m=m1+… +mk，

易證得f(v)是圖T5的優(yōu)美標(biāo)號。

圖7 鏈圖T5Fig.7 Chain graph T5

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

[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]吳麗鴻，王世英.幾類圖的優(yōu)美性研究[J].太原師范學(xué)院學(xué)報(bào):自然科學(xué)版，2011，10(3):50-53.

[4]楊顯文，于敬蓮.關(guān)于圖 C4∪Fm，4的優(yōu)美性[J].吉林廣播電視大學(xué)學(xué)報(bào)，2002，58(2):54-56.

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

[8]曾一平.等長輻射樹Tnm的優(yōu)美性[J].太原重型機(jī)械學(xué)院學(xué)報(bào)，1988，9(1):9-16.

[9]王衛(wèi)兵，楊徐昕.一類偶階圖的邊優(yōu)美性[J].數(shù)學(xué)理論與應(yīng)用，2010，30(2):81-84.

[10]吳躍生，徐保根.關(guān)于圖的優(yōu)美性[J].安徽大學(xué)學(xué)報(bào)，2011，35(5):14-17.

[11]李武裝，苗宗文，嚴(yán)謙泰.幾類有趣圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2011，41(4):234-239.