吳躍生

（華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西南昌330013）

本文所討論的圖均為無(wú)向簡(jiǎn)單圖，V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集。

定義1[1]對(duì)于一個(gè)圖G=(V，E)如果存在一個(gè)單射，使得對(duì)所有邊e=(u，v) ∈E(G)，由導(dǎo)出的是一個(gè)雙射，則稱G是優(yōu)美圖，θ是G的一組優(yōu)美標(biāo)號(hào)，稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值。

定義2[1]在圖G每個(gè)頂點(diǎn)都粘接了r條懸掛邊（r≥1的整數(shù)）所得到的圖，稱為圖G的r-冠，圖G的1-冠，稱做圖G的冠。

定義3V(G)=(v1，v2，…，vn)的每個(gè)頂點(diǎn)vi都粘接了ri條懸掛邊（ri為非負(fù)整數(shù)，i=1，2，…，n）所得到的圖，稱為圖G的(r1，r2，…，rn)-冠，簡(jiǎn)記為G(r1，r2，…，rn)。特別地，當(dāng)r1=r2=…=rn=r時(shí)，稱為圖G的r-冠。圖G的θ-冠就是圖G。

定義4[2]G是一個(gè)優(yōu)美二部圖，其優(yōu)美標(biāo)號(hào)為θ，V(G)劃分成兩個(gè)集合X，Y，如果mv∈aXxθ(v)＜mv∈iYnθ(v)，則稱θ是G的交錯(cuò)標(biāo)號(hào)。稱G是在交錯(cuò)標(biāo)號(hào)θ下的交錯(cuò)圖。

事實(shí)上，G是在交錯(cuò)標(biāo)號(hào)θ下的交錯(cuò)圖就是文[1]中所定義的平衡圖。

馬克杰等在文[1]中證明了圖P1∨Pn的優(yōu)美性，并證明了圖P1∨Pn的r-冠的優(yōu)美性，由此猜想:任意優(yōu)美圖的r-冠都是優(yōu)美圖。

文獻(xiàn)[3-6]在上猜想的引導(dǎo)下，證明了一些優(yōu)美圖（如圈Cn((n≡0)，3(m od4 ))）的r-冠是優(yōu)美的。

文獻(xiàn)[7]給出了圈Cn的(r1，r2，…，rn)-冠的定義，討論了當(dāng)n=7，8 時(shí)，圈Cn的 (r1，r2，…，rn)-冠的優(yōu)美性。本文討論了當(dāng)n=4h時(shí)，圈Cn的(r1，r2，…，rn)-冠的優(yōu)美性。

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

定理 當(dāng)n=4h，h為非零自然數(shù)，ri為任意自然數(shù)（i=1，2，…，4h），圈Cn的(r1，r2，…，rn)-冠的頂點(diǎn)集如圖1所示，V(Cn)=(v1，v2，…，vn)，與vi鄰接的端點(diǎn)（或葉）記為xij(vi∈V(Cn)，j=1，2，…，ri)，當(dāng)時(shí)，圈Cn的 (r1，r2，…，rn)-冠是交錯(cuò)圖。

證明 當(dāng)n=4h，h≤1時(shí)，下面用構(gòu)造性的方法給出圈Cn的(r1，r2，…，rn)-冠的兩種交錯(cuò)（平衡）標(biāo)號(hào)。第一種交錯(cuò)（平衡）標(biāo)號(hào)。定義圈Cn的(r1，r2，…，rn)-冠的頂點(diǎn)標(biāo)號(hào)θ為

因此θ是C4h的(r1，r2，…，r4h)-冠的優(yōu)美標(biāo)號(hào)。即C4h的 (r1，r2，…，r4h)-冠是優(yōu)美圖。

令:

因此θ是C4h的(r1，r2，…，r4h)-冠的交錯(cuò)標(biāo)號(hào)。即C4h的 (r1，r2，…，r4h)-冠是交錯(cuò)圖。

第二種交錯(cuò)（平衡）標(biāo)號(hào)。下面定義圈Cn的(r1，r2，…，rn)-冠的另一種標(biāo)號(hào)交錯(cuò)（平衡）θ1為:（設(shè)θ是C4h的(r1，r2，…，r4h)-冠的第一種交錯(cuò)標(biāo)號(hào)）

證明類似第一種優(yōu)美標(biāo)號(hào)，此處略。

在定理中，令r1=r2=…=r4h=r，有

推論1C4h的r-冠是交錯(cuò)圖。

引理[1]交錯(cuò)圖至少有4種不同的交錯(cuò)標(biāo)號(hào)（即標(biāo)號(hào)為θ的交錯(cuò)圖可以派生出另外3種不同的交錯(cuò)標(biāo)號(hào)）。

推論2 當(dāng)n=4h，h為非零自然數(shù)，ri為任意自然數(shù)（i=1，2，…，4h），當(dāng)時(shí)，圈Cn的

(r1，r2，…，rn)-冠至少有8種不同的交錯(cuò)標(biāo)號(hào)。

例 下面根據(jù)定理給出圈C12的(2 ，2，0，4，0，1，0，0，2，0，5，0)-冠的兩種交錯(cuò)標(biāo)號(hào)，如圖2，圖3所示。

[1]馬杰克.優(yōu)美圖[M].北京:北京大學(xué)出版社，1991.

[2]楊顯文，張志尚.一類交錯(cuò)圖并的優(yōu)美性[J].吉林工程技術(shù)師范學(xué)院學(xué)報(bào):自然科學(xué)版，2007，23（6）:8-10.

[3]武建春.圖D2，4k與它的r-冠的優(yōu)美性[J].內(nèi)蒙古電大學(xué)刊，2002（1）:34.

[4]曾朝英，武建春.關(guān)于優(yōu)美圖Cn和Cn⊙k1的r-冠的優(yōu)美性[J].集寧師專學(xué)報(bào)，2000，22（4）:4-7.

[5]曾朝英.圖ω4k，n的r-冠的優(yōu)美性[J].集寧師專學(xué)報(bào)，2001，23（4）:4-6.

[6]胡紅亮.圖Cn及其r-冠的新的優(yōu)美標(biāo)號(hào)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2010，26（3）:454-457.

[7]吳躍生，李詠秋.關(guān)于圈Cn的（r1，r2，…，rn）-冠（n=7，8）的優(yōu)美性[J].阜陽(yáng)師范學(xué)院學(xué)報(bào):自然科學(xué)版，2010，27（3）:20-23.