[[alternative]]具有最大無符號拉普拉斯譜半徑的圖及其相關主題之研究

博士[[abstract]]對一個(簡單) 圖G, 我們稱矩陣Q(G)= D(G) + A(G) 為圖G 的無符號拉普拉斯, 其中A(G),D(G) 分別為G 的鄰接矩陣及頂點度數對角矩陣。圖G 的頂點u,v 如果滿足N(u)-{v}= N(v)-{u} 這個條件, 則被稱為屬於G 的相同鄰域等價類, 其中N(u) 為由u 的鄰接點所構成的集合。根據鄰域等價關係這個概念, 及利用G 的線圖當媒介, 在這篇論文我們針對擁有固定點和邊數的圖, 在「具有最大無符號拉普拉斯譜半徑的圖」這個研究題目上, 有一些值得關注的進展。 一個重要的已知結果為: 具有最大無符號拉普拉斯譜半徑的圖是一個閾圖, 而一個閾圖若是連通則是一個(度) 極大圖, 若是不連通則是一個極大圖與一個零圖的聯集, 因此我們把焦點放在極大圖上。首先, 我們得到了一些極大圖(或閾圖) 達到最大無符號拉普拉斯譜半徑的必要條件, 進而完全決定了在固定m 條邊m−k (k =0,1,2,3) 個頂點的狀況下達到最大無符號拉普拉斯譜半徑的圖。 接著我們針對有相同點和邊個數的圖, 研究擁有二個及三個鄰域等價類的極大圖的結構, 並比較它們所對應無符號拉普拉斯譜半徑的大小關係, 其間有一些不等式及等式被發現。在探討擁有二個鄰域等價類極大圖的無符號拉普拉斯譜半徑時, 我們也得到了一些有趣的性質: 我們可以具體找出此類圖的無符號拉普拉斯譜半徑ρ(Q(G)) 介於那兩個連續正整數之間, 即可找到正整數k 使得k≤ ρ(Q(G)) <k+ 1, 並能得到此類圖的無符號拉普拉斯具有整數譜的充要條件, 且藉著在數論中一對Pell’s 方程式的解得到一些屬於此類擁有無符號拉普拉斯整數譜的例子。 在圖譜理論中, 長久以來一直有個經典的問題尚未解決, 也就是決定在固定連通圖的點數為n, 邊數為n+ k 的狀況下達到最大譜半徑(ρ(A(G))) 的圖; 關於這個問題, 有學者僅對3 ≤ k<n− 3 提出部分猜想, 而針對我們研究的主題, 這個擁有最大無符號拉普拉斯譜半徑的連通圖(點的個數為n, 邊個數為n+ k, 且3 ≤ k≤ n− 3) 將會在這篇論文中被完全決定, 答案就是著名的極大圖Hn,k。 最後, 我們用自己的方法重新考慮一個極大圖的拉普拉斯譜, 並提出一些觀察。另外我們也比較極大圖Hn,n−3 及Gn,n−3 的鄰接矩陣譜半徑, 發現前者是比較小。[[abstract]]By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)= D(G) + A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. Vertices u,v of G are said to belong to the same neighborhood equivalence class of Gif N(u)-{v} = N(v)-{u}, where N(u) denotes the set of neighbors of u in G. Using the concept of neighborhood equivalence classes and with the line graph as a major tool, in this thesis we make a study of the problem of determining connected graphs (or, not necessarily connected graphs) that maximize the signless Laplacian spectral radius over all connected graphs (or, graphs) with given numbers of vertices and edges, and make progress in several respects. We focus attention to (degree) maximal graphs as it is known that optimal graphs for the connected (respectively, not necessarily connected) case of the signless Laplacian spectral radius maximization problem are maximal (respectively, thresh¬old); and every threshold graph is either a maximal graph or the union of a maximal graph and a null graph. For a maximal graph Gwith nvertices and r distinct vertex degrees δr >δr−1 >...>δ1, it is proved that ρ(Q(G)) <ρ(Q(H)) for some maximal graph H with n+ 1 (respectively, n) vertices and the same number of edges as G if either G has precisely two dominating vertices or there exists an integer i, 2≤i≤�r/2�, such that δi + δr+1−i ≤ n+ 1 (respectively, if there exist positive integers i,l, with l+ 2 ≤ i ≤ �r/2 �, such that δi + δr+1−i ≤ δl + δr−l + 1). Thus, we obtain a set of necessary conditions for a maximal graph (or, a threshold graph) to be optimal graphs for the maximization problems. As a consequence, we also determine completely graphs that maximize the signless Laplacian spectral radius over the class of (not necessarily connected) graphs with medges and m−kvertices for k= 0,1,2,3. Interesting inequality relations and (number-theoretic) equality relations are found between the cardinalities of neighborhood equivalence classes for a pair of maximal graphs, one with two neighborhood equivalence classes and the other with three neighborhood equivalence classes, that have the same number of vertices and the same number of edges. For such pair of maximal graphs we compare their signless Laplacian spectral radii. We also find a localization result for the signless spectral radius of a maximal graph with two neighborhood equivalence classes of the form: k≤ ρ(Q(G)) <k+ 1, where kis an integer. The question of when the signless Laplacian spectrum of a maximal graph with two neighborhood equivalence classes is made up of nonnegative integers is also touched upon. iv In spectral graph theory the problem of determining connected graphs that maximize the adjacency spectral radius over the class of connected graphs with n vertices and n + k edges is an unresolved classic problem and there is a well-known conjecture associated with it for the case k < n− 3, which is still open. For the corresponding problem for the signless Laplacian spectral radius we have the following solution for the case k ≤ n− 3: For any pair of positive integers n,k, if 3 ≤ k ≤ n − 3, then Hn,k, the graph obtained from the star K1,n−1 by joining a vertex of degree 1 to k+ 1 other vertices of degree 1, is the unique connected graph that maximizes the signless Laplacian spectral radius over all connected graphs with n vertices and n+ k edges. Using our methods, we also reconsider the Laplacian spectrum of a maximal graph, give some observations in connection with the related extremal problem of finding a graph that maximizes the number of length-2 paths among graphs (or connected graphs) with given numbers of vertices and edges, and show that the ad¬jacency spectral radius of the maximal graph Hn,n−3 is less than that of the maximal graph Gn,n−3.[[tableofcontents]]Contents CHAPTER ONE Introduction 1 CHAPTER TWO Some Preliminary Results 7 2.1. Some graph-theoretic notions . . . . . . . . . 7 2.2. Preparations in matrix theory . . . . . . . . 9 2.3. Graph matrices . . . . . . . . . . . . . 12 2.4. Threshold graphs and maximal graphs . . . . 16 2.5. Spectral radii maximizing graphs . . . . . . 20 2.6. A useful result on graph spectra. . . . . . 24 2.7. A special kind of Diophantine equations . . 30 CHAPTER THREE Graphs that Maximize the Signless Laplacian Spectral Radius When m − n Is Small 34 3.1. When is the graph G − uv + pq maximal? . . . 34 3.2. Effects of edge replacement on the signless Laplacian spectral radius 43 3.3. Maximizing the signless Laplacian spectral radius when m − n is small 57 CHAPTER FOUR Maximal Graphs with Two or Three Neighborhood Equivalence Classes 75 4.1. The signless Laplacian spectral radii of maximal graphs in M (n, m; 2) 75 4.2. When M (n, m; 2) and M (n, m; 3) are both nonempty 82 CHAPTER FIVE Connected Graphs with Maximal Signless Laplacian Spectral Radius: the One-Dominating-Vertex Case 100 5.1. Solution for the one-dominating-vertex case 100 5.2. The proof . . . . . . . . . . . . . . 102 CHAPTER SIX Some Additional Results 111 6.1. Laplacian spectrum of a maximal graph . . . 111 6.2. A comparison between ρ(A(Gn,n−3)) and ρ(A(Hn,n−3)) 115 6.3. Graphs with maximum number of length-2 paths 118 Bibliography 127[[note]]學號: 892150045, 學年度: 9