具有公共邊的雙圈圖的奇優美標號及其算法

劉家保， 王 林， 陸一南

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

0 引 言

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

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具有奇優美標號，且稱圖G為奇優美圖［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）是奇優美圖。

證明 雙圈圖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｝的雙射函數。

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

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｝的雙射函數。

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

綜上所述，定理1得證。

3 結束語

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

［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］ 劉家保，潘向峰.輪形圖和扇形圖的優美性［J］.安徽大學學報：自然科學版，2009，133（4）：11－13.

［4］ 嚴謙泰.積圖Pn×Pm的奇優美性和奇強協調性［J］.系統科學與數學，2010，30（3）：341－348.

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

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

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

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

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