[[alternative]]簡約圖譜矩陣理論與其應用

博士[[abstract]]對一個(簡單)圖G而言，所謂G的鄰域等價關係是指在V(G)上如下定義的(等價)關係: ~G 被定義為: u ~G v若且惟若 N(u){v} = N(v){u}, 其中N(u) 為與u相鄰的點所構成的集合。這篇論文中主要目的為闡釋鄰域等價關係是一個重要的概念，藉由它，我們可以得到簡化的公式，更清楚地分析或了解圖譜理論中的某些結果與問題。 以A(G) 表示G 的鄰接矩陣，D(G) 表示 G 的度對角矩陣，則G 的拉普拉斯為D(G)-A(G), G 的無符號拉普拉斯為A(G)+D(G)。 G 的簡約拉普拉斯矩陣是Δ(G)-B(G)，G 的簡約無符號拉普拉斯矩陣是Δ(G)+B(G)，其中B(G)是G的簡約鄰接矩陣，Δ(G)是一個對角矩陣，其對角線素為在同一鄰域等價類之點的共同度。如果一個圖是連通的而且它的度數列並沒有被其他的連通圖的度數列超越，則稱此圖為一個(度)極大圖。 在本論文我們首先重證了一些由數學家Goddard、 Schneider或Haynsworth所發現有關分割矩陣的舊定，進而推導出一個新定理。此定理是有關一個具有下列特性的方塊隨機矩陣的譜:(一)每一非對角方塊的元素皆相同;(二)每一對角方塊擁有相同的非對角元素及相同的對角元素。利用這個新定理與簡約圖矩陣的概念我們對圖矩陣的譜的研究在下列五項獲得良好的進展: 1.圖矩陣的譜是簡約圖矩陣的譜與一些多重集合的聯集，這些多重集合是與圖的鄰域等價類的個數與屬同一等價類的點的共同度有關。 2.我們找到極大圖的無符號拉普拉斯特徵多項式得一個公式。利用此公式我們證得極大圖的簡約無符號拉普拉斯的特徵值與圖的點的相異度的某種交錯關係。另外我們也比較Hn,k與Gn,k這兩個極大圖的無符號拉普拉斯的譜半徑的大小關係。 3.(1)若G是擁有n個點的連通圖且具備有下列其中一個條 件，則n-2是其無符號拉普拉斯的第二大特徵值: (a) G 至少有兩個點與其他點皆相連。 (b) G 有兩個互不相連但與其他點皆相連的點。 (c) G 可由Kn-1加一個垂邊獲得。 (2)若G是一個擁有n個點的連通圖， 憶於完全圖Kn且n-2是它的 無符號 拉普拉斯的特徵值，則n-2的代數重數最多是n-2。 等號成立的充分且必要條件為G=C(2,n-2) 或 n=4 及G=C4。 4.我們獲得到一個極大圖在具有固定的點與邊之連結圖中擁有最大譜 半徑的一個必要條件。 5.針對已知的極大圖的拉普拉斯的譜的描述，給予另一種新證明。[[abstract]]For a (simple) graph G, by the neighborhood equivalence relation on G we mean the equivalence relation on V(G) given by : if and only if , where denotes the set of neighbors of u in G. An aim of this thesis is to support the view that the neighborhood equivalence relation is an important concept, which provides a vantage point to formulate, analyze or better understand results and problems in the spectral graph theory. Based on an old theorem of Haynsworth , which can also be ascribed to Goddard and Schneider, we first derive a new result on the spectrum of a block- stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. Then we apply the result and the concept of reduced graph matrices to study the spectra of the usual graph matrices (including, in particular, the adjacency matrix, the Laplacian and the signless Laplacian) by partitioning the vertex set of the graph according to the neighborhood equivalence relation and make progress in the following five items : 1. The spectra of various graph matrices are given in terms of the spectra of the corresponding reduced graph matrices and certain multi-sets which depend on the cardinalities of the neighborhood equivalence classes and the common degree for vertices belonging to the same neighborhood equivalence class. 2. A formula for the characteristic polynomial of the signless Laplacian of a (degree) maximal graph is obtained and used to derive a (weak) interlacing relation between its reduced signless Laplacian eigenvalues and the degrees of its vertex. The signlsee Laplacian spectral radii of the well-known maximal graphs and (for ) are compared. 3. It is proved that a connected graph G of order n has n-2 as the second largest signless Laplacian eigenvalue if one of the following is satisfied : (a) G has at least two dominating vertices (which is the case if );(b) G has a pair of duplicate vertices with common degree n-2; (c) G is the graph obtained from by adding a pendant edge. It is also shown that for a connected graph of order , different from , if n-2 is a signless Laplacian eigenvalue, then the multiplicity of n-2 is at most n-2 with equality if and only if G=C(2,n-2) or n=4 and G=C4. 4. A set of necessary conditions for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges is obtained. 5. A new proof for the (known) description of the Laplacian spectrum of a maximal graph is offered.[[tableofcontents]]Contents Chapter 1. Introduction 1 Chapter 2. Preliminaries 5 2.1. Definitions and notation . . . . . . . . . . . . . . 5 2.2. Some preparations in matrix theory . . . . . . . . . 6 2.2.1. The relation between determinant and circuit product. . . . . . . . . . . . . . . . . . . . . . . . . .6 2.2.2. Real symmetric matrices . . . . . . . . . . . . . . 9 2.2.3. Nonnegative matrices . . . . . . . . . . . . . . . 10 2.3. Graphs with maximal adjacency or signless Laplacian spectral radii. . . . . . . . . . . . . . . . . . . . . . 12 2.4. Maximal graph and threshold graph . . . . . . . . .. 20 2.5. Reduced graph matrices . . . . . . . . . . . . . . 26 Chapter 3. Some results on partitioned matrices with applications to graph spectra. . . . . . . . . 28 3.1. A revisit of some classical results on partitioned matrices. . . . . . . . . . . . . . . . . . . . . . . . .28 3.2. A new result on partitioned matrices with applications to graph spectra. . . . . . . . . . . . . . . . . . . . . 34 3.3. The second largest signless Laplacian eigenvalue . . 45 3.4. A necessary condition for a signless Laplacian maximizing graph. . . . . . . . . . . . . . . . . . . . . 49 Chapter 4. The reduced signless Laplacian eigenvalues of a maximal graph. . . . . .55 4.1. The reduced signless Laplacian characteristic polynomial of a maximal graph. . . . . .. .. . . . . . . 55 4.2. Localization inequalities . . . . . . . . . . . . . . . . . . . . . . 62 4.3. Some consequences . . . . . . . . . . . . . . . . . 72 4.4. Answers to some natural questions . . . . . . . . . 74 Chapter 5. A comparison between the spectral radii of two well-known maximal graphs79 5.1. The maximal graphs Gn,k and Hn,k. . . .. . . . . . 79 5.2. A comparison between adjacency spectral radii . . .. 80 5.3. A comparison between signless Laplacian spectral radii . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Chapter 6. Some observations on the Laplacian spectrum of a maximal graph 95 6.1. The Laplacian spectrum of a maximal graph . .. . . .95 6.2. Further observations . . . . . . . . . . . . . . 100 References 104 List of Figures Figure 1. A threshold graph with vertex-weights and threshold.. . . . . . . . . . . . . . . . . . . . . . . . 20 Figure 2. The digraph of B(x) (with loops omitted) . . . . . . . . . . . . . . . . . . . . . . . . 59[[note]]學號: 892150011, 學年度: 9