齒輪圖冠的優(yōu)美性*

劉育興，李淑萍，彭慧彥

(贛南師范大學 數(shù)學與計算機科學學院，江西 贛州 341000)

1 引言

1963年,G.Ringel在文獻[1]中提出了一個猜想:完備圖K2n+1能夠被分解成2n+1個子圖，這些子圖都與一個給定的有n條的樹同構(gòu).這一猜想被稱為Ringel猜想. 1966年,A.Rosa在文獻[2]中在證明Ringel猜想的過程中,引入了β值這一工具,1972年,S.W.Golomb在文獻[3]中把β值稱為優(yōu)美標號,并一直沿用至今.

在文獻[2]中A.Rosa首次提出猜想:所有的樹都是優(yōu)美樹.這就是著名的優(yōu)美樹猜想.這一猜想起初是與Ringel猜想有密切的聯(lián)系而受到人們的關(guān)注, 然而由于它自身的原因, 不久就成為一個非常著名的猜想. 這個猜想至今沒有被證明或否定.

雖然具有一定規(guī)則結(jié)構(gòu)的許多圖類都是優(yōu)美圖，但是V.N.Bhat-Nayak與S.K.Gokhale在[4]中證明了有無窮多類圖不是優(yōu)美圖,并且在文獻[2]中A.Rosa證明了:如果每一個頂點的度都是偶數(shù)且邊數(shù)同余于1或2(模4), 則這個圖一定不是優(yōu)美圖.特別地,圈C4n+1和C4n+2都不是優(yōu)美圖.

圖的標號問題是組合數(shù)學中一個熱門課題.它不僅屬于圖論領(lǐng)域,也屬于設(shè)計理論的范疇. 圖的優(yōu)美標號是圖的標號問題中的一種,有著廣泛的應(yīng)用.圖的優(yōu)美標號主要應(yīng)用于編碼設(shè)計、變壓器箱設(shè)計、射電天文學、晶體結(jié)構(gòu)中原子位置的測定和導彈控制碼的設(shè)計等方面.研究圖的優(yōu)美性,即尋找圖的優(yōu)美標號.優(yōu)美圖是圖論中極有趣的研究課題之一.

由于優(yōu)美圖的趣味性和應(yīng)用性,自1972年S.W.Golomb明確給出優(yōu)美圖的定義以來,很快得到了人們的重視,獲得了不少研究成果[1-7].

盡管在許多研究者的不懈努力下已經(jīng)取得了豐碩的成果，但是對于圖的優(yōu)美性的研究仍有大量的工作要做,已經(jīng)證明判定任意一個圖是否為優(yōu)美圖是一個NP-困難問題,即對于給定的一個圖,判定它是否為優(yōu)美圖,不存在一個有效算法. 因此,對于圖的優(yōu)美性的研究還有很長的路要走.

2 定義及定理

文中所討論的圖G(V,E)都是簡單無向圖.V(G)和E(G)分別表示G的頂點集和邊集.|E(G)|(或|E|)表示圖G的邊數(shù),N+是正整數(shù)集合.文中未說明的符號及術(shù)語均同于文獻[1].

定義1[1]對于一個圖G(V,E),若存在單射f:V(G)→{0,1,2,…,|E|-1},使得導出映射f′(uv)=|f(u)-f(v)|是E(G)→{1,2,3,…,|E|-1}的雙射,則稱G為優(yōu)美圖,而f稱為G的一個優(yōu)美標號.

定義2[1]由圈Cn的每個頂點都與同一個不在Cn上的頂點相連接所得到的圖，叫做輪，記作Wn.

文獻[2]中馬克杰和馮成進已經(jīng)證明了下述定理.

3 定理1的證明

下面證明定理1,我們根據(jù)n的取值分以下3種情形進行討論.

圖1 三個特殊齒輪圖的冠的優(yōu)美標號

圖2 齒輪圖的冠

圖3 兩個特殊齒輪圖的冠的優(yōu)美標號