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

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

2、n的分解體，當n是偶數(shù)時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是奇數(shù))。Vilfred等給出了猜想：當n為素數(shù)并且n>m時Pm×Pn為素圖，Sundaram等證明了這個猜想而且還證明了當n為素數(shù)時，Pn×Pn是素圖。Carlson證明了廣義的Books和Cn-Snakes圖是素圖。Yao，Ch

3、eng，Zhongfu等人給出了這樣的結(jié)論：如果一個圖的最大的度數(shù)至少是n/2(n為頂點數(shù))時，這個圖為素圖。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)