k-超競賽圖的度序列.pdf

1、圖論是數(shù)學(xué)的一個分支,尤其是離散數(shù)學(xué)的一個重要分支,它在物理、化學(xué)、天文、地理、生物學(xué)以及在計算機(jī)科學(xué)中有著很廣泛的應(yīng)用.它最吸引人的特色是它蘊(yùn)涵著大量強(qiáng)有力的思想、漂亮的圖形和巧妙的論證,而它解決問題的方法也是千變?nèi)f化,非常靈活,所以解決圖論中的問題不僅需要知識,而且更需要智慧和靈活深入的思考.
　　 k-超競賽圖是圖論中的一個很有趣的研究課題,是一般競賽圖的推廣,有著較好的研究價值和較實際的應(yīng)用前景.早在很久之前外國的一些著

2、名學(xué)者如,Barbut,Bialostcki以及Frankl就對超競賽圖做了一定的研究,并且他們也提出了一個重要的結(jié)論:每一個競賽圖都有一個Hamilton路,每一個強(qiáng)競賽圖都有一個Hamilton圈.Bondy也通過超競賽圖與Hamilton路之間的關(guān)系解決了用一次循環(huán)賽所得的得分序列決定名次的問題.在1953年社會學(xué)家Landau也通過超競賽圖研究了小雞與小雞之間統(tǒng)治與啄咬次序之間的關(guān)系.
　　 周國飛,張克民對k-超競賽圖

3、的度序列做了相應(yīng)的研究,設(shè)k=3,n>3,S=(s1,s2,…,si)為非降的非負(fù)整數(shù)序列,則S為某一個3-超競賽圖的度序列當(dāng)且僅當(dāng):對任意的r(1≤r≤n),有∑si≥(r2)(n-2,k-2),且當(dāng)r=n時取等號.并提出了猜想:設(shè)k≥4,n>k,S=(s1,s2,…,si)為非降的非負(fù)整數(shù)序列,則S為某一個k-超競賽圖的度序列當(dāng)且僅當(dāng):對任意的r(1≤r≤n),有∑si≥(r2)(n-2,k-2),且當(dāng)r=n時取等號.