若干圖的素標號和FFI集問題研究.pdf

1、標號問題是圖論領域很重要的研究課題之一，本文利用算法與分析中的回溯與分支限界的理論設計程序求解了幾類圖的標號問題，將計算機構造證明與數學證明相結合研究了兩類標號問題：素標號、FFI集。 素標號是由Entringer提出，由Tout,Dabboucy和Howalla給出了樹是素圖的猜想。目前，經過證明是素圖的樹有：路徑，星圖，毛毛蟲，完全二叉樹，蜘蛛圖，橄欖樹，所有頂點數小于50的樹。其它的具有素標號的圖包括：所有的圈，C2k和C

2、n的分解體，當n是偶數時Wn，完全圖Kn(n≥4)，F(xiàn)ans，Helms，F(xiàn)lowers，Stars，K2,n與K3，n(n≠3，7)，Books，Sn(m)，Gn(×)Pm，Pn×K2—(當且僅當n=2或n是奇數)。Vilfred等給出了猜想：當n為素數并且n>m時Pm×Pn為素圖，Sundaram等證明了這個猜想而且還證明了當n為素數時，Pn×Pn是素圖。Carlson證明了廣義的Books和Cn-Snakes圖是素圖。Yao，Ch

3、eng，Zhongfu等人給出了這樣的結論：如果一個圖的最大的度數至少是n/2(n為頂點數)時，這個圖為素圖。FFI集是由HarrisKwong，S.M.Lee，HoKuenNg在2006年首次提出的概念，即：{if(G)｜f是圖G的Friendly標號}并給出了FFI(Cn)，S.M.Lee等證明了下列圖的FI(G)：樹，圈，棱柱，M(o)bius梯等。隨后WaiCheeShiu，HarrisKwong證明了P2×Pn具有FFI(G)