圖的最小特征值.pdf

1、譜圖理論主要研究圖的矩陣表示的譜性質(zhì)，建立譜性質(zhì)與圖的結(jié)構(gòu)性質(zhì)或結(jié)構(gòu)參數(shù)之間的聯(lián)系，利用圖的譜性質(zhì)刻畫圖的結(jié)構(gòu)性質(zhì)，是代數(shù)圖論和組合矩陣論一個(gè)重要研究內(nèi)容。
　　 縱觀當(dāng)今國內(nèi)外的譜圖理論研究，主要工作集中在圖的一些極端譜參數(shù)和極值譜性質(zhì)上。具體而言，圖的極端譜參數(shù)包括研究圖的各種矩陣表示的譜半徑、最小特征值、次大和次小特征值以及它們具有特定意義的組合形式。它們通常比其它特征值蘊(yùn)含了更多的結(jié)構(gòu)信息，所以更受人們的關(guān)注。圖的極值譜

2、性質(zhì)是指刻畫譜參數(shù)(通常是極端譜參數(shù))達(dá)到某些極值條件(如最大、最小、臨界值)時(shí)所具有的性質(zhì)。最為常見的極值譜性質(zhì)問題是特征值的極圖問題，即刻畫在某個(gè)確定的圖類(即給定某一或某些參數(shù)的圖)中某一特征值達(dá)到極大或極小的圖。人們?cè)噲D通過分析極圖的結(jié)構(gòu)，來探求圖的譜參數(shù)與結(jié)構(gòu)參數(shù)之間的關(guān)系。這一想法已成為研究者實(shí)現(xiàn)譜圖理論研究目標(biāo)的主要途徑。
　　 近三十年來，關(guān)于譜半徑的極值譜性質(zhì)研究已相對(duì)成熟。研究者刻畫了各種結(jié)構(gòu)參數(shù)與譜半徑之間

3、的聯(lián)系。作為另一個(gè)極端特征值，圖的最小特征值同樣能夠很好地反映圖的結(jié)構(gòu)信息，具有很好的研究意義。圖的Laplace矩陣的最小非平凡特征值(即代數(shù)連通度)是刻畫連通性的重要參數(shù)[37]，已有豐富的研究成果。相比之下，其它兩類矩陣表示的最小特征值的研究工作則相對(duì)較少。事實(shí)上，它們同樣是刻畫圖結(jié)構(gòu)的有力工具。例如，圖的最小特征值可用于判別一個(gè)圖是否是某個(gè)圖的線圖[21]，最小Q-特征值可作為圖的二部性的一個(gè)度量[31，32]等。因此，從最小特

4、征值的角度刻畫圖的結(jié)構(gòu)是非常有意義的。本文主要討論圖的(鄰接)最小特征值和最小Q-特征值的極值譜性質(zhì)，刻畫它們與圖結(jié)構(gòu)之間的關(guān)系。
　　 本文的第一章首先介紹圖譜理論的研究背景，其次介紹基本的概念和記號(hào)，最后介紹所要研究的問題，它們的進(jìn)展，以及本文所取得的主要結(jié)果。
　　 本文的第二章討論了圖的鄰接最小特征值與兩個(gè)重要結(jié)構(gòu)參數(shù)(割點(diǎn)數(shù)與割邊數(shù))之間的關(guān)系，分別刻畫了給定割點(diǎn)數(shù)和割邊數(shù)的連通圖中最小特征值的極小圖。此外，我

5、們還分別確定了給定割點(diǎn)數(shù)和割邊數(shù)的二部圖中譜半徑的極大圖。
　　 本文的第三章研究了圖的補(bǔ)與最小特征值之間的關(guān)系，刻畫了在所有樹的補(bǔ)圖中最小特征值的極小圖和所有單圈圖的補(bǔ)圖中最小特征值的極小圖，試圖從補(bǔ)圖的最小特征值角度探討圖的結(jié)構(gòu)性質(zhì)。
　　 本文的第四章主要討論圖的最小Q-特征值。在4.1節(jié)，研究了圖的第一Q-特征向量的組合結(jié)構(gòu)性質(zhì)，刻畫了在若干結(jié)構(gòu)擾動(dòng)下最小Q-特征值的變化情況。利用這些性質(zhì)，在4.2節(jié)，研究了給定