關于一類樹的優美標號

劉家保,呂寧寧,余國鋒

(安徽新華學院公共基礎部,安徽合肥230088)

0 引 言

優美圖是圖論中極其有趣的內容,是一類特殊的簡單無向圖.優美圖的研究始于1963年 G·Ringel提出的一個猜想和1966年A·Rosa的一篇論文[1].1972年,S.W.Golomb明確給出了優美圖的概念.優美圖的優美標號可應用于編碼理論、通信網絡、射電天文學、導彈控制碼設計等方面,一直以來深受人們的重視,迄今,已有許多這方面的成果[1-6].但由于對優美圖的研究缺乏一個系統和有力的工具,所以目前只能對一些特殊的圖類探索其優美性.

1 預備知識

定義1 圖 G的一個頂點標號L,是指從V(G)到 {0,1,2,…,|V|},且u,v不同時,有L(u)≠L(V).

定義2 簡單圖 G的一個優美標號,是指 G的一個頂點標號L,它滿足：當 G的邊e=uv時,由L′(e)=|L(u)-L(V)|決定的邊標號L′,會分配給各邊以不同的標號,這時L′為 E(G)到{1,2,…,|E|}的雙射.若簡單圖G有優美標號L,則稱 G為優美圖.

圖1 圖 的圖示

為了敘述方便,本文規定,文中所討論的圖均為簡單無向圖,其他未加說明的定義和符號均請參考文獻[7].

2 結論及其證明

情況一：當 h≡1(mod2),(不妨設 h=2s-1).給出圖的各頂點的標點遞推算法A如下：

證明 設 S1={L(ai)|1≤i≤m},S2={L(bi)|1≤j≤n},S3={L(cj)|1≤j≤h}=S31∪S32,其中 S31={L(cj)|1≤j≤h},j為奇數},S32={L(cj)|1≤j≤h,j為偶數},則有算法 A可得:

很清楚每個頂點的標號各不相同,并且滿足Max{L(V)}=m+n+h=|E|,因此L是從頂點集合V()到 {0,1,…,m+n+h}的一一映射函數,從而頂點集與集合 {0,1,2,…,m+n+h}構成單射.

從而 L′(chb1)＜L′(chb2)＜ …＜L′(a2c0)＜L′(a1c0)

邊標號的集合:

即1＜2＜…＜2n-1＜m+n+h,從而所有不同的邊有不同的標號,綜上所述圖的邊集與集合 {1,2,…,m+n+h}構成一一對應.

情況二：當 n≡0(mod2),(不妨設 h=2s)給出圖的各頂點的標點遞推算法B如下：

算法B：L (ai) =m+n+h-i+1,(i=1,2,…,m)

證明 設S1={L(ai)|1≤i≤m},S2={L(bj)|1≤j≤n},S3={L(cj)|1≤j≤h}=S31∪S32,其中 S31={L(cj)|1≤j≤h,j為奇數},S32={L(cj)|1≤j≤h,j為偶數},則有算法B可得：

很……