若干圖標號問題的研究.pdf

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

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

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

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