吳躍生, 毛國珍

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

1 引言與概念

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

定義1[2]在含有 n個頂點的路Pn上,當且僅當兩點的距離為3時增加一條邊,所得到的圖叫做 P3n.

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

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

2 主要結果及其證明

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

證明:當 n≥4時,設圖 C3∪P3n的頂點集如圖1所示.

下面給出圖 C3∪P3n的標號θ:

圖1

(1)當n=6k時,

θ(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)當n=6k+1時,

θ(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)當n=6k+2時,

θ(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)當n=6k+3時,

θ(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)當n=6k+4時,

θ(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)當n=6k+5時,

θ(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的情況給予證明,其余類似可證.

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

圖2

圖3

圖4

圖5

圖6

圖7

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

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

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

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

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

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

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