若干圖的素標(biāo)號(hào)和FFI集問題研究.pdf

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

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

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