林育青，鐘發(fā)勝，曹 蓉，童細(xì)心

（汕頭職業(yè)技術(shù)學(xué)院自然科學(xué)系，廣東 汕頭 515041）

0 引言

優(yōu)美圖的提出始于1963年G.Ringel[1]的一個(gè)猜想和1967 A.Rosa[2]的一篇論文.1972年，S.W.Golomb[3]明確給出了優(yōu)美圖的定義.1982年，F(xiàn)ank Hsu D[4]引入圖的強(qiáng)協(xié)調(diào)標(biāo)號(hào)；1994年，Gnanajoethi提出另一個(gè)猜想：“每棵樹都是奇優(yōu)美的”[5-6]，又推動(dòng)了對(duì)圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性的研究，也取得了一些成果[7-18].但由于缺乏一個(gè)系統(tǒng)和有力的工具，迄今，只能對(duì)一些特殊圖探索其奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性.本文給出了圖的定義，討論了圖的奇優(yōu)美性與奇強(qiáng)協(xié)調(diào)性并給出了標(biāo)號(hào)算法.

定義 1[5]對(duì)于簡(jiǎn)單圖 G＝（V，E），如果存在一個(gè)映射滿足：1）f是單射；2）有：

則稱圖G是奇優(yōu)美圖，f稱為G的奇優(yōu)美標(biāo)號(hào).

定義 2[4]對(duì)于簡(jiǎn)單圖 G＝（V，E），如果存在一個(gè)映射滿足：1）f是單射；2），令f（uv）＝f（u）＋f（v）有：

則稱圖G是奇強(qiáng)協(xié)調(diào)的，f稱為G的奇強(qiáng)協(xié)調(diào)標(biāo)號(hào).

定義3[7]在含有n個(gè)頂點(diǎn)的路Pn上，當(dāng)且僅當(dāng)兩點(diǎn)的距離為m（m≥2）時(shí)增加一條邊，這樣所得到的圖稱為.

定義4在含有n個(gè)頂點(diǎn)的路Pn上，當(dāng)且僅當(dāng)兩點(diǎn)的距離為m（m≥2）時(shí)增加一條長(zhǎng)度為2的邊，這樣所得到的圖稱為的細(xì)分圖，記為.

圖 1 圖

本文所討論的圖均為無向簡(jiǎn)單圖，其它未加說明的定義和符號(hào)均來自文獻(xiàn)[19].

1 主要結(jié)果及證明

下面分兩種情形證明.

（1）v2i－1＝vi，i，i＝1，2，…，k；

（2）v2i＝vi＋1，i，i＝1，2，…，k；

（3）v2i－1，2i＋1＝vi，i＋1，i＝1，2，…，k－1；

（4）v2i，2i＋2＝vi＋1，i－1，i＝1，2，…，k－1.

圖 2 圖P（2k，2）的頂點(diǎn)標(biāo)記

下面給出P（2k，2）的頂點(diǎn)標(biāo)號(hào)算法A：

算法A（1）f（vi，i＋1）＝（12k－7）－6i，i＝1，2，…，k－1；

（2）f（vi，i）＝6i－6，i＝1，2，…，k

（3）f（vi＋1，i）＝（12k－5）－6i，i＝1，2，…，k

（4）f（vi＋2，i）＝6i－2，i＝1，2，…，k－1

下面驗(yàn)證算法A是圖P（2k，2）的一個(gè)奇優(yōu)美標(biāo)號(hào)算法，從而也是圖的一個(gè)奇優(yōu)美標(biāo)號(hào)算法.

圖 3 圖 P（2k＋1，2）的頂點(diǎn)標(biāo)記

綜上，由引理2.3、2.4及定義2，當(dāng)n＝2k＋1時(shí)，圖是奇強(qiáng)協(xié)調(diào)圖，即情形4成立.

2 實(shí)例

圖4 圖的奇優(yōu)美標(biāo)號(hào)

圖 5 圖的奇優(yōu)美標(biāo)號(hào)

圖6 圖的奇強(qiáng)協(xié)調(diào)標(biāo)號(hào)

圖 7 圖的奇強(qiáng)協(xié)調(diào)標(biāo)號(hào)