幾類廣義冠圖的研究.pdf

1、圖譜理論在計算機科學、通信網(wǎng)絡、量子化學等眾多學科中都有應用，由圖的特征多項式可以直接得到圖的譜，因此研究得到圖的特征多項式對于研究這些學科都很有益。圖的鄰接矩陣A(G)表示了圖中頂點與頂點之間的鄰接關系，鄰接矩陣的特征多項式稱為鄰接特征多項式。圖的度對角矩陣是對角線上為每個頂點的度的對角矩陣，記為D(G)。Laplacian矩陣記為L(G)=D(G)-A(G)，Laplacian矩陣的特征多項式稱為Laplacian特征多項式；sig

2、nless Laplacian矩陣記為Q(G)=D(G)+A(G)，signless Laplacian矩陣的特征多項式稱為signless Laplacian特征多項式。圖的各項特征多項式的特征根及其重數(shù)稱為圖的譜，分別為鄰接譜、Laplacian譜和signless Laplacian譜。同譜而又非同構的圖稱為同譜圖，分別為鄰接同譜圖（記為A-同譜圖）、Laplacian同譜圖（記為L-同譜圖）和signless Laplacian

3、同譜圖（記為Q-?同譜圖）。
　　冠圖是通過多個圖進行圖操作所得到的復雜圖，剖分圖是在每條邊上新添加一個頂點所得到的圖。本文將冠圖廣義化并融合了剖分圖操作，構造了兩種新的廣義冠圖：廣義剖分冠邊圖S(G)(○-)m∧iHi和廣義剖分冠點圖S(G)☉m∧iHi。應用分塊矩陣、舒爾補、矩陣的冠值等計算并證明了這兩類廣義冠圖的鄰接特征多項式、Laplacian特征多項式和signless Laplacian特征多項式。作為應用還得到了在特

4、殊情況下這兩種廣義冠圖的生成樹數(shù)目和Kirchhoff指數(shù)，并給出了計算生成樹數(shù)目的例子。隨后還得到了一系列的鄰接同譜圖、Laplacian同譜圖和signless Laplacian同譜圖圖簇，并給出了例子。
　　本文的主要成果有：
　　(1)定義了一類新的廣義冠圖--廣義剖分冠邊圖S(G)(○-)m∧iHi。計算并證明了它的各項特征多項式。
　　(2)計算并證明了在圖G為r-正則圖，圖H1,…Hm均為圖H時構造的非

5、廣義的剖分冠邊圖S(G)(○-)H的L-譜、生成樹個數(shù)和Kirchhoff指數(shù)。并給出了計算生成樹數(shù)目的例子。
　　(3)得到了一系列鄰接同譜、Laplacian同譜和signless Laplacian同譜的廣義剖分冠邊圖圖簇，并給出了同譜圖的例子。
　　(4)定義了一類新的廣義冠圖--廣義剖分冠點圖S(G)(○-)m∧iHi。計算并證明了它的各項特征多項式。
　　(5)計算并證明了在圖G為r-正則圖，圖H1,…Hn