一致仙人掌樹(shù)的Felicitous性質(zhì)

楊思華　姚兵

摘 要 利用較小的具有集有序Felicitous性質(zhì)的樹(shù)構(gòu)造較大規(guī)模的具有Felicitous性質(zhì)的樹(shù)，并揭示了集有序Felicitous樹(shù)與集有序優(yōu)美樹(shù)的等價(jià)關(guān)系.

關(guān)鍵詞 一致仙人掌樹(shù)；Felicitous標(biāo)號(hào)；集有序Felicitous標(biāo)號(hào)；集有序優(yōu)美標(biāo)號(hào)

中圖分類(lèi)號(hào) O1575文獻(xiàn)標(biāo)識(shí)碼 A文章編號(hào) 10002537（2014）03008704

1996年，Rosa[1]提出了一個(gè)猜想：每一棵樹(shù)都是優(yōu)美樹(shù).后來(lái)，Bermond[2]又提出了猜想：所有龍蝦樹(shù)都是優(yōu)美樹(shù).關(guān)于這兩個(gè)猜想已經(jīng)有了很多結(jié)果，但是一直沒(méi)有徹底地解決.SinMin Lee[3]等人于1991年提出了猜想：每一棵樹(shù)都是Felicitous樹(shù).該猜想與優(yōu)美樹(shù)猜想具有同等的理論價(jià)值，而且具有相同的難度，都是NPhard問(wèn)題[412].對(duì)于數(shù)學(xué)猜想的進(jìn)攻，導(dǎo)致圖的標(biāo)號(hào)迅速發(fā)展成為當(dāng)今圖論學(xué)科中十分活躍的分支，它在編碼理論、通訊網(wǎng)絡(luò)、物流等方面均有著重要應(yīng)用.

1 預(yù)備知識(shí)

本文涉及的圖均為有限、無(wú)向簡(jiǎn)單圖.文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均來(lái)自文獻(xiàn)[13]. 為敘述簡(jiǎn)便，我們把一個(gè)有p個(gè)頂點(diǎn)q條邊的連通圖記為（p，q）圖.記號(hào)[m，n]表示非負(fù)整數(shù)集合{m，m+1，m+2，…，n}，其中m和n均為整數(shù)，且滿足0≤m

定義1 設(shè)G是（p，q）圖，若存在一個(gè)單射f：V（G）→[0，q]，使得邊標(biāo)號(hào)集合{f（uv）|uv∈E（G）}=[0，q-1]，其中邊標(biāo)號(hào)為f（uv）=f（u）+f（v）（mod q），那么稱G是Felicitous圖，并稱f是G的一個(gè)Felicitous標(biāo)號(hào).

對(duì)于定義1中的圖G和Felicitous標(biāo)號(hào)f，以下簡(jiǎn)記頂點(diǎn)標(biāo)號(hào)集合f（V（G））={f（u）|u∈V（G）}，邊標(biāo)號(hào)集合f（E（G））={f（u）+f（v）|uv∈E（G）}，以及f（E（G））（mod q）={f（uv）|uv∈E（G）}.

定義2 設(shè)（X，Y）是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，如果G有一個(gè)Felicitous標(biāo)號(hào)f，使得max{f（x）|x∈X}

定義3 設(shè)G是（p，q）圖，若存在一個(gè)單射f：V（G）→[0，q]，使得邊標(biāo)號(hào)集合{f（uv）|uv∈E（G）}=[1，q]，其中邊標(biāo)號(hào)為f（uv）=|f（u）-f（v）|，那么稱G是優(yōu)美圖，并稱f是G的一個(gè)優(yōu)美標(biāo)號(hào).進(jìn)一步，設(shè)（X，Y）是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，若G有一個(gè)優(yōu)美標(biāo)號(hào)f，使得f（X）

摘 要 利用較小的具有集有序Felicitous性質(zhì)的樹(shù)構(gòu)造較大規(guī)模的具有Felicitous性質(zhì)的樹(shù)，并揭示了集有序Felicitous樹(shù)與集有序優(yōu)美樹(shù)的等價(jià)關(guān)系.

關(guān)鍵詞 一致仙人掌樹(shù)；Felicitous標(biāo)號(hào)；集有序Felicitous標(biāo)號(hào)；集有序優(yōu)美標(biāo)號(hào)

中圖分類(lèi)號(hào) O1575文獻(xiàn)標(biāo)識(shí)碼 A文章編號(hào) 10002537（2014）03008704

1996年，Rosa[1]提出了一個(gè)猜想：每一棵樹(shù)都是優(yōu)美樹(shù).后來(lái)，Bermond[2]又提出了猜想：所有龍蝦樹(shù)都是優(yōu)美樹(shù).關(guān)于這兩個(gè)猜想已經(jīng)有了很多結(jié)果，但是一直沒(méi)有徹底地解決.SinMin Lee[3]等人于1991年提出了猜想：每一棵樹(shù)都是Felicitous樹(shù).該猜想與優(yōu)美樹(shù)猜想具有同等的理論價(jià)值，而且具有相同的難度，都是NPhard問(wèn)題[412].對(duì)于數(shù)學(xué)猜想的進(jìn)攻，導(dǎo)致圖的標(biāo)號(hào)迅速發(fā)展成為當(dāng)今圖論學(xué)科中十分活躍的分支，它在編碼理論、通訊網(wǎng)絡(luò)、物流等方面均有著重要應(yīng)用.

1 預(yù)備知識(shí)

本文涉及的圖均為有限、無(wú)向簡(jiǎn)單圖.文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均來(lái)自文獻(xiàn)[13]. 為敘述簡(jiǎn)便，我們把一個(gè)有p個(gè)頂點(diǎn)q條邊的連通圖記為（p，q）圖.記號(hào)[m，n]表示非負(fù)整數(shù)集合{m，m+1，m+2，…，n}，其中m和n均為整數(shù)，且滿足0≤m

定義1 設(shè)G是（p，q）圖，若存在一個(gè)單射f：V（G）→[0，q]，使得邊標(biāo)號(hào)集合{f（uv）|uv∈E（G）}=[0，q-1]，其中邊標(biāo)號(hào)為f（uv）=f（u）+f（v）（mod q），那么稱G是Felicitous圖，并稱f是G的一個(gè)Felicitous標(biāo)號(hào).

對(duì)于定義1中的圖G和Felicitous標(biāo)號(hào)f，以下簡(jiǎn)記頂點(diǎn)標(biāo)號(hào)集合f（V（G））={f（u）|u∈V（G）}，邊標(biāo)號(hào)集合f（E（G））={f（u）+f（v）|uv∈E（G）}，以及f（E（G））（mod q）={f（uv）|uv∈E（G）}.

定義2 設(shè)（X，Y）是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，如果G有一個(gè)Felicitous標(biāo)號(hào)f，使得max{f（x）|x∈X}

定義3 設(shè)G是（p，q）圖，若存在一個(gè)單射f：V（G）→[0，q]，使得邊標(biāo)號(hào)集合{f（uv）|uv∈E（G）}=[1，q]，其中邊標(biāo)號(hào)為f（uv）=|f（u）-f（v）|，那么稱G是優(yōu)美圖，并稱f是G的一個(gè)優(yōu)美標(biāo)號(hào).進(jìn)一步，設(shè)（X，Y）是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，若G有一個(gè)優(yōu)美標(biāo)號(hào)f，使得f（X）

摘 要 利用較小的具有集有序Felicitous性質(zhì)的樹(shù)構(gòu)造較大規(guī)模的具有Felicitous性質(zhì)的樹(shù)，并揭示了集有序Felicitous樹(shù)與集有序優(yōu)美樹(shù)的等價(jià)關(guān)系.

關(guān)鍵詞 一致仙人掌樹(shù)；Felicitous標(biāo)號(hào)；集有序Felicitous標(biāo)號(hào)；集有序優(yōu)美標(biāo)號(hào)

中圖分類(lèi)號(hào) O1575文獻(xiàn)標(biāo)識(shí)碼 A文章編號(hào) 10002537（2014）03008704

1996年，Rosa[1]提出了一個(gè)猜想：每一棵樹(shù)都是優(yōu)美樹(shù).后來(lái)，Bermond[2]又提出了猜想：所有龍蝦樹(shù)都是優(yōu)美樹(shù).關(guān)于這兩個(gè)猜想已經(jīng)有了很多結(jié)果，但是一直沒(méi)有徹底地解決.SinMin Lee[3]等人于1991年提出了猜想：每一棵樹(shù)都是Felicitous樹(shù).該猜想與優(yōu)美樹(shù)猜想具有同等的理論價(jià)值，而且具有相同的難度，都是NPhard問(wèn)題[412].對(duì)于數(shù)學(xué)猜想的進(jìn)攻，導(dǎo)致圖的標(biāo)號(hào)迅速發(fā)展成為當(dāng)今圖論學(xué)科中十分活躍的分支，它在編碼理論、通訊網(wǎng)絡(luò)、物流等方面均有著重要應(yīng)用.

1 預(yù)備知識(shí)

本文涉及的圖均為有限、無(wú)向簡(jiǎn)單圖.文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均來(lái)自文獻(xiàn)[13]. 為敘述簡(jiǎn)便，我們把一個(gè)有p個(gè)頂點(diǎn)q條邊的連通圖記為（p，q）圖.記號(hào)[m，n]表示非負(fù)整數(shù)集合{m，m+1，m+2，…，n}，其中m和n均為整數(shù)，且滿足0≤m

定義1 設(shè)G是（p，q）圖，若存在一個(gè)單射f：V（G）→[0，q]，使得邊標(biāo)號(hào)集合{f（uv）|uv∈E（G）}=[0，q-1]，其中邊標(biāo)號(hào)為f（uv）=f（u）+f（v）（mod q），那么稱G是Felicitous圖，并稱f是G的一個(gè)Felicitous標(biāo)號(hào).

對(duì)于定義1中的圖G和Felicitous標(biāo)號(hào)f，以下簡(jiǎn)記頂點(diǎn)標(biāo)號(hào)集合f（V（G））={f（u）|u∈V（G）}，邊標(biāo)號(hào)集合f（E（G））={f（u）+f（v）|uv∈E（G）}，以及f（E（G））（mod q）={f（uv）|uv∈E（G）}.

定義2 設(shè)（X，Y）是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，如果G有一個(gè)Felicitous標(biāo)號(hào)f，使得max{f（x）|x∈X}

定義3 設(shè)G是（p，q）圖，若存在一個(gè)單射f：V（G）→[0，q]，使得邊標(biāo)號(hào)集合{f（uv）|uv∈E（G）}=[1，q]，其中邊標(biāo)號(hào)為f（uv）=|f（u）-f（v）|，那么稱G是優(yōu)美圖，并稱f是G的一個(gè)優(yōu)美標(biāo)號(hào).進(jìn)一步，設(shè)（X，Y）是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，若G有一個(gè)優(yōu)美標(biāo)號(hào)f，使得f（X）