幾類廣義冠圖的研究.pdf

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

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

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

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

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