關(guān)于圖 C3∪P3n的優(yōu)美性

吳躍生, 毛國珍

(1.華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西南昌 330013; 2.江西贛州市第三中學(xué), 江西贛州 340001)

1 引言與概念

本文所討論的圖均為無向簡單圖,V(G)和 E(G)分別表示圖 G的頂點(diǎn)集和邊集,未說明的符號及術(shù)語均同文[1].

定義1[2]在含有 n個(gè)頂點(diǎn)的路Pn上,當(dāng)且僅當(dāng)兩點(diǎn)的距離為3時(shí)增加一條邊,所得到的圖叫做 P3n.

圖P3n的優(yōu)美性[2-7]是眾多學(xué)者研究的對象.本文研究不交并圖 C3∪P3n的優(yōu)美性.

定義2[1]對于一個(gè)圖 G=(V,E),如果存在一個(gè)單射θ:V(G)→{0,1,2,…,|E(G)|}使得對所有邊e=(u,v)∈E(G),由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的 E(G)→{1,2,…,|E(G)|}是一個(gè)雙射,則稱 G是優(yōu)美圖,θ是G的一組優(yōu)美標(biāo)號,稱θ′為G的邊上的由θ導(dǎo)出的誘導(dǎo)值.

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

定理1 當(dāng) n≥4時(shí),C3∪P3n是優(yōu)美圖.

證明:當(dāng) n≥4時(shí),設(shè)圖 C3∪P3n的頂點(diǎn)集如圖1所示.

下面給出圖 C3∪P3n的標(biāo)號θ:

圖1

(1)當(dāng)n=6k時(shí),

θ(x0)=1,θ(x1)=4,θ(x2)=3

θ(y6j)=7j,θ(y6j+1)=12k-5j-1,

θ(y6j+2)=7j+2,

θ(y6j+3)=12k-5j-2,

θ(y6j+4)=7j+5,θ(y6j+5)=12k-5j-3,其中 j=0,1,2,…,k-1

(2)當(dāng)n=6k+1時(shí),

θ(x0)=1,θ(x1)=4,θ(x2)=3

θ(y6j)=7j,其中 j=0,1,2,…,k,θ(y6j+1)=12k-5j+1,θ(y6j+2)=7j+2,

θ(y6j+3)=12k-5j,θ(y6j+4)=7j+5,θ(y6j+5)=12k-5j-1,其中 j=0,1,2,…,k-1,

(3)當(dāng)n=6k+2時(shí),

θ(x0)=5,θ(x1)=7,θ(x2)=8

θ(y0)=0,θ(y1)=12k+3,θ(y6j+2)=7j+2,θ(y3)=12k+2,θ(y6j+4)=7j+4,θ(y6j+5)=12k-5j-1,θ(y6j+6)=7j+6,θ(y6j+7)=12k-5j-2,其中 j=0,1,2,…,k-1

θ(y6j+9)=12k-5j-3,其中 j=0,1,2,…,k-2

(4)當(dāng)n=6k+3時(shí),

θ(x0)=1,θ(x1)=4,θ(x2)=3

θ(y0)=0,θ(y1)=12k+5,θ(y2)=2,θ(y6j+3)=12k-5j+4,θ(y6j+4)=7j+5,

θ(y6j+5)=12k-5j+3,θ(y6j+6)=7j+8,θ(y6j+7)=12k-5j+2,θ(y6j+8)=7j+10,

其中 j=0,1,2,…,k-1

(5)當(dāng)n=6k+4時(shí),

θ(x0)=5,θ(x1)=7,θ(x2)=8

θ(y0)=0,θ(y1)=12k+7,θ(y6j+2)=7j+2,θ(y3)=12k+6,其中 j=0,1,2,…k,

θ(y6j+4)=7j+4,θ(y6j+5)=12k-5j+3,θ(y6j+6)=7j+6,θ(y6j+7)=12k-5j+2,θ(y6j+9)=12k-5j+1,其中 j=0,1,2,…,k-1.

(6)當(dāng)n=6k+5時(shí),

θ(x0)=5,θ(x1)=7,θ(x2)=8

θ(y0)=0,θ(y1)=12k+9,θ(y6j+2)=7j+2,θ(y3)=12k+8,

θ(y6j+4)=7j+4,其中 j=0,1,2,…,k,θ(y6j+5)=12k-5j+5,θ(y6j+6)=7j+6,

θ(y6j+7)=12k-5j+4,θ(y6j+9)=12k-5j+3,其中 j=0,1,2,…,k-1.

只對 n=6k的情況給予證明,其余類似可證.

上面的標(biāo)號,對yj(j=0,1,2,…6k-1)來說,每個(gè)偶數(shù)頂點(diǎn)的標(biāo)號是從小到大排列,最大的標(biāo)號是7k-2;每個(gè)奇數(shù)頂點(diǎn)的標(biāo)號是從大到小排列,最小的標(biāo)號是7k+2;又θ(xi)≠θ(yj)(i=0,1,2;j=0,1,2,…6k-1).因此,存在一個(gè)單射由θ′(e)=|θ(u)-θ(v)|導(dǎo)出的為雙射;所以θ是的優(yōu)美標(biāo)號.

圖2

圖3

圖4

圖5

圖6

圖7

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

[2]林育青.關(guān)于圖 P3n的優(yōu)美性 [J].華南師范大學(xué)學(xué)報(bào) (自然科學(xué)版),2000,(3):21-24.

[3]嚴(yán)謙泰,李武裝.關(guān)于圖 P3n優(yōu)美性的研究 [J].數(shù)學(xué)的實(shí)踐與認(rèn)識,2005,(4):131-139.

[4]王云,張秉儒.論圖 P3n的優(yōu)美性 [J].電腦知識與技術(shù),2007,(6):1661-1664.

[5]鄧懷敏,林育青.圖 P3n的優(yōu)美標(biāo)號 [J].新疆大學(xué)學(xué)報(bào) (自然科學(xué)版),2000,(2):12-16.

[6]付明彥,劉小冬,王力工.再論圖 P3n的優(yōu)美性 [J].西南民族大學(xué)學(xué)報(bào)自然科學(xué)版,2007,(3):456-459.

[7]嚴(yán)謙泰.張忠輔,關(guān)于 P3n的優(yōu)美性 [[J].數(shù)學(xué)研究與評論.2004,24(2):89-92.