劉家保， 王 林， 陸一南

（安徽新華學院公共課教學部，安徽合肥 230088）

0 引 言

關于圖的優(yōu)美性，文獻［1］提出“所有的樹都是優(yōu)美的”著名優(yōu)美樹猜想，奇優(yōu)美標號是一類特殊的優(yōu)美標號，具有奇優(yōu)美標號的圖類是奇優(yōu)美圖。文獻［2］給出了優(yōu)美圖的定義。到目前為止，國內外已取得很多關于優(yōu)美圖的研究成果［1－9］。本文研究一類具有公共邊的雙圈圖奇優(yōu)美標號。

1 基本概念

定義1 對于一個簡單圖G＝（V，E）有a個頂點和b條邊，存在函數L：V（G）→｛0，1，2，…，2b－1｝是單射的，誘導出函數L′：E（G）→｛1，3，…，2b－1｝，且L′（e＝uv）＝｜L（u）－L（v）｜是雙射的，稱圖G具有奇優(yōu)美標號，且稱圖G為奇優(yōu)美圖［1］。

定義2 2個圈圖Cn共享一條公共邊的圖類，記為雙圈圖D（n），設Cn∩Cn＝e＝uv，u，v∈V（D（n）），e＝uv∈E（D（n）），雙圈圖D（n）滿足以下條件：

（2）頂點集V（D（n））＝｛vi｜1≤i≤n｝，頂點數｜V（D（n））｜＝2n－2。

（3）邊集E（D（n））＝｛vivi＋1｜1≤i≤2n－3｝∪｛v2n－2v1｝∪｛v（n＋2）／2v3n／2｝，邊數｜E（D（n））｜＝2n－1。

2 主要結果

定理1 對?n∈N＊，n≡0（mod 4）或者n≡2（mod 4），雙圈圖D（n）是奇優(yōu)美圖。

證明 雙圈圖D（n）頂點數為｜V（D（n））｜＝2n－2，邊數為｜E（D（n））｜＝2n－1，2個單圈圖公共的一條邊為e＝v（n＋2）／2v3n／2。定義函數L： V（D（n））→｛0，1，2，…，2｜E（D（n））｜－1｝＝｛0，1，2，…，4n－3｝，邊標號定義為L′（piqj）＝｜L（pi）－L（qj）｜，其中pq∈E（D（n）），給出圖D（n）各頂點的標號算法。

2.1 情形1（n≡0（mod 4））

（1）當1≤i≤n＋1時，有

（2）當n＋2≤i≤3n／2時，有

首先證明L是從頂點集V（D（n））到｛0，1，2，…，4n－3｝的單射函數。

令A＝｛L（vi）｜1≤i≤2n－2｝，則

因此，A＝A1∪A2∪A3∪A4∪A5∪A6是所有頂點標號的集合，且有：

由上可知，A?｛0，1，2，…，4n－3｝，所有頂點的標號是各不相同的，所以L是一個從V（D（n））到｛0，1，2，…，4n－3｝的單射函數。

其次，證明L′是從E（D（n））到｛1，3，…，4n－ 3｝的雙射函數。

令B＝｛L′（vivi＋1）｜1≤i≤2n－3｝∪｛L′（v（n＋2）／2v3n／2）｝∪｛L′（v2n－2v1）｝，則有：

因為

所以

因此，B＝B1∪B2∪B3是所有邊的標號的集合，且有：

由上述可知，每條邊的標號是各不相同的，且邊的標號的集合為｛1，3，…，4n－3｝，所以L′是一個從E（D（n））到｛1，3，…，4n－3｝的雙射函數。

根據奇優(yōu)美標號的定義，對?n∈N＊，且圖D（n）的n確定，雙圈圖在n≡0（mod 4）的情形下是奇優(yōu)美圖。

2.2 情形2（n≡2（mod 4））

（1）當1≤i≤n＋1時，有

（2）當n＋2≤i≤3n／2時，有

下面證明L是從頂點集V（D（n））到｛0，1，2，…，4n－3｝的單射函數。

令C＝｛L（vi）｜1≤i≤2n－2｝，則所有頂點標號的集合C?｛0，1，2，…，4n－3｝，所有頂點的標號是各不相同的，所以L是一個從V（D（n））到｛0，1，2，…，4n－3｝的單射函數。

同理證明L′是從E（D（n））到｛1，3，…，4n－3｝的雙射函數。

令D＝｛L（vivi＋1）｜1≤i≤2n－3｝∪｛L（v（n＋2）／2v3n／2）｝∪｛L（v2n－2v1）｝，有

由上述可知，所有邊的標號的集合D＝D1∪D2∪D3＝｛1，3，…，4n－3｝，每條邊的標號是各不相同的，所以L′是一個從E（D（n））到｛1，3，…，4n－3｝的雙射函數。

根據奇優(yōu)美標號的定義，對?n∈N＊，且圖D（n）的n確定，雙圈圖D（n）在n≡2（mod 4）的情形下是奇優(yōu)美圖。

綜上所述，定理1得證。

3 結束語

本文探索了一類具有公共邊的雙圈圖D（n）的奇優(yōu)美標號，運用算法設計與分析的理論思想設計了求解本類雙圈圖頂點和邊標號的算法，并獲得了任意頂點數雙圈圖的奇優(yōu)美標號，最后對雙圈圖D（n）是否為奇優(yōu)美圖進行了嚴格論證。

［1］ Rosa A.On certain valuations of the vertices of a graph［C］／／Theory of Graphs（Int Symposium，Rome，July 1966），Gordon and Breach，N Y and Dunod Paris，1967：349－355.

［2］ Golomb S W.How to number a graph：graph theory and computing［M］.New York：Academic Press，1972：23－27.

［3］ 劉家保，潘向峰.輪形圖和扇形圖的優(yōu)美性［J］.安徽大學學報：自然科學版，2009，133（4）：11－13.

［4］ 嚴謙泰.積圖Pn×Pm的奇優(yōu)美性和奇強協(xié)調性［J］.系統(tǒng)科學與數學，2010，30（3）：341－348.

［5］ 劉家保，張 季，聶東明.一類新的聯(lián)圖的優(yōu)美標號算法［J］.汕頭大學學報：自然科學版，2011，26（1）：8－10.

［6］ 郭文富.關于圖B（m，n，p）的優(yōu)美性［J］.數學雜志，1995，15（3）：345－351.

［7］ 嚴謙泰.關于P2r，2mP2r，2m的優(yōu)美標號［J］.系統(tǒng)科學與數學，2006，26（5）：513－517.

［8］ 劉家保，王 林.一類優(yōu)美圖的計算機算法［J］.汕頭大學學報：自然科學版，2011，26（2）：23－28.

［9］ 劉家保，王 林，陸一南.雙圈圖G（n，m）的奇優(yōu)美標號及其算法［J］.合肥工業(yè)大學學報：自然科學版，2012，35（5）：708－710.