圖論中和圖標號問題的研究.pdf

1、圖論是數(shù)學的一個分支，特別是離散數(shù)學的一個重要分支，它在物理、化學、天文、地理、生物學，尤其是計算機科學中有非常廣泛的應用. 本文主要研究圖的標號問題，圖的標號問題起始于1966年A.Rosa的著名的優(yōu)美樹猜想.一個圖的頂點標號是圖的頂點集到整數(shù)集的映射.而根據(jù)對映射的不同的要求，產(chǎn)生了各種各樣的圖的標號問題.1988年，F(xiàn).Harary給出(整)和圖的標號；1990年，Bolland，Laskar，Yurner和Domke把和

2、圖推廣到模和圖.2000年，Sonntag和Teichert把(整)和圖的概念推廣到超圖上. 和圖標號在射電天文學及計算機網(wǎng)絡理論中有著廣泛的應用.本文研究了三類標號：(整)和圖標號、模和圖標號、(整)和超圖標號.分別解決了三類標號中的一些問題和猜想.主要工作概括如下： 給出完全三部圖K1,1,rr≥3的(整)和數(shù)、完全三部圖K1,r,rr≥2(整)和數(shù)的一個上下界；并證明了扇圖Fn及任意個扇圖在中心處相交構(gòu)成的圖是整和

3、圖，同時荷蘭風車Dn也是和圖、整和圖、模和圖.Chen[6]猜想樹是整和圖，本文證明了花樹是整和圖；用粘合法推廣了一類整和圖(任意一個整和圖和三叉樹的沾合)；給出單位圖(σ(G)=1)和星圖的并，任意星圖的并是整和圖. Sutton，Miller，Ryan和Slamin[24]中提出了兩個問題：扇圖(Fn)和Kn，n的模和數(shù).本文證明了扇圖(Fn)不是模和圖，并給出當n偶數(shù)時，ρ(Fn)=2；ρ(Kn，n)=n.Sonntag和