若干圖標(biāo)號(hào)問(wèn)題的研究.pdf

1、圖的標(biāo)號(hào)問(wèn)題起始于1966年A．Rosa的著名的優(yōu)美樹猜想．一個(gè)圖的頂點(diǎn)標(biāo)號(hào)是圖的頂點(diǎn)集到整數(shù)集的映射，而邊標(biāo)號(hào)則是圖的邊集到整數(shù)集的映射．根據(jù)對(duì)映射的不同要求，產(chǎn)生了各種類型的圖的標(biāo)號(hào)問(wèn)題．本文對(duì)圖的Skolem優(yōu)美標(biāo)號(hào)、超幻和標(biāo)號(hào)和調(diào)和標(biāo)號(hào)三類問(wèn)題進(jìn)行研究，分別解決了這三類標(biāo)號(hào)中的一些問(wèn)題和猜想，取得了較好的結(jié)果． 優(yōu)美標(biāo)號(hào)在射電天文學(xué)及計(jì)算機(jī)網(wǎng)絡(luò)理論中有著廣泛的應(yīng)用．Skolem優(yōu)美標(biāo)號(hào)是優(yōu)美標(biāo)號(hào)的一個(gè)衍變．k-星圖是由k

2、個(gè)任意大小的星圖組成的不連通圖．對(duì)k-星圖的優(yōu)美性，Kishore猜想當(dāng)且僅當(dāng)有一個(gè)星是偶星或者k≡0，1(mod 4)時(shí)，k-星圖是Skolem優(yōu)美的．Choudum和Kishore等人證明了這個(gè)猜想在k≤5時(shí)成立．本文對(duì)任意的k-星圖的Skolem優(yōu)美性進(jìn)行研究，針對(duì)k-星圖和Skolem優(yōu)美標(biāo)號(hào)的特點(diǎn)，設(shè)計(jì)了相應(yīng)的分支限界搜索策略；對(duì)于有一個(gè)星是偶星或者k≡0，1(mod 4)的各種情形，分別搜索到了在該情形下Skolem優(yōu)美標(biāo)號(hào)

3、的共有特點(diǎn)，從中總結(jié)出相應(yīng)的從圖的頂點(diǎn)集V到整數(shù)集(1，2，…，|V|}的1-1映射函數(shù)，從而證明了Kishore猜想對(duì)任意的k都成立． 超幻和標(biāo)號(hào)是幻類型標(biāo)號(hào)的一種衍變．Figueroa-Centeno等證明了當(dāng)n為奇數(shù)且n≠5(mod 8)時(shí)，Book圖玩不是超邊幻和圖，并猜想對(duì)n≥5，當(dāng)且僅當(dāng)n是偶數(shù)或n≡5(mod 8)時(shí)，B<,n>是超邊幻和圖．本文證明了當(dāng)n為大于等于6的偶數(shù)時(shí)，B<,n>是超邊幻和圖．本文還研究了K

4、nodel圖W<,3,n>和Flower Snark及其相關(guān)圖F<,n>的超點(diǎn)幻和標(biāo)號(hào)，證明了當(dāng)且僅當(dāng)n三0(mod 4)時(shí)，Knodel圖W<,3,n>是超點(diǎn)幻和圖；并證明了所有的Flower Snark及相關(guān)圖F<,n>都是超點(diǎn)幻和圖． 調(diào)和標(biāo)號(hào)是為解決糾錯(cuò)碼的問(wèn)題而由優(yōu)美標(biāo)號(hào)衍變而來(lái)的．徐士達(dá)證明了當(dāng)且僅當(dāng)p≠2(mod 4)時(shí)，三角蛇圖是調(diào)和圖．本文證明了所有的雙三角蛇圖都是調(diào)和圖．Deb和Limye提出猜想：所有的多貝