對一個(簡單) 圖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 的鄰接矩陣譜半徑, 發現前者是比較小。

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&not;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&not;jacency spectral radius of the maximal graph Hn,n−3 is less than that of the maximal graph Gn,n−3.

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

[1] R. Ahlswede, G.O.H. Katona, Graphs with the maximum number of adjacent pairs of edges, Acta Math. Acad. Sci. Hungar. 32 (1978) 97-220. 
[2] M. Aouchiche, F.K. Bell, D. Cvetkovi´c, P. Hansen, P. Rowlinson, S. Simi´c, 
D. Stevanovi´c, Variable neighborhood search for extremal graphs, 16. Some conjectures related to the largest eigenvalue of a graph, European J. Oper. Res. 191 (2008) 661-676. 
[3] M. Aouchiche, P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl. (2009), doi:10.1016/j.laa.2009.06.015. 
[4] F.K. Bell, On the maximal index of connected graphs, Linear Algebra Appl. 144 (1991) 135-151. 
[5] F. Boesch, C. Suffel, R. Tindell, F. Harary, The neighborhood inclusion struc¬ture of a graph, Mathematical and Computer Modelling 17(1993) 25-28. 
[6] R.A. Brualdi, A.J. Hoffman, On the spectral radius of (0, 1)-matrices, Linear Algebra Appl. 65 (1985) 133-146. 
[7] R.A. Brualdi, E.S. Solheid, On the spectral radius of connected graphs, Publ. Inst. Math (Beograd) (N.S.) 39(53) (1986), 45-54. 
[8] T.-C.	Chang, B.-S. Tam, Graphs with maximal signless Laplacian spectral radius, Linear Algebra Appl. 432 (2010), 1708-1733. 
[9] T.-C. Chang, B.-S. Tam, S.-H. Wu, Theorems on partitioned matrices revisited 
and their applications to graph spectra, submitted for publication.
127

[10] D. Cvetkovi´c, Spectral theory of graphs based on the signless Laplacian, Re¬search Report, 2010. 
[11] D. Cvetkovi´c, M. Doob, H. Sachs, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995. 
[12] D. Cvetkovi´c, P. Rowlinson, On connected graphs with maximal index, Publ. Inst. Math. (Beograd)(N.S.) 44(58)(1988), 29-34. 
[13] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Eigenspaces of graphs, Cambridge Uni¬versity Press, Cambridge, 1997. 
[14] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Spectral generalizations of line graphs: on graphs with least eigenvalue −2, Cambridge University Press, Cambridge, 2004. 
[15] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007), 155-171. 
[16] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Eigenvalue bounds for the signless Lapla¬cian, Publ. Inst. Math. (Beograd) (N.S.) 81(95)(2007), 11-27. 
[17] D. Cvetkovi´c, S.K. Simi´c, Towards a spectral theory of graphs based on the signless Laplacian I, Publ. Inst. Math. (Beograd), 81(99)(2009),19-33. 
[18] D. Cvetkovi´c, S.K. Simi´c, Towards a spectral theory of graphs based on the signless Laplacian II, Linear Algebra Appl., doi: 10.1016/j.laa.2009.05.020, to appear. 
[19] D. Cvetkovi´c, S.K. Simi´c, Towards a spectral theory of graphs based on the signless Laplacian III, Applicable Analysis and Discrete Math., to appear. 
[20] E.R. van Dam, W. Haemers, Which graphs are determined by their spectrum ? Linear Algebra Appl. 373 (2003) 241-272. 
[21] K.C. Das, Sharp lower bounds on the Laplacian eigenvalues of trees, Linear Algebra Appl. 384 (2004), 155-169. 
[22] K.C. Das, The Laplacian spectrum of a graph, Computers & Math. Appl. 48 (2004), 715-724. 
[23] K.C. Das, On conjectures involving second largest signless Laplacian eigenvalue of graphs, Linear Algebra Appl., to appear. 
[24] Y.-Z. Fan, On spectral integral variations of graphs,	Linear and Multilinear Algebra 50 (2002) 133-142. 
[25] Y.-Z. Fan, Spectral integral variations of degree maximal graphs, Linear and Multilinear Algebra 51 (2003) 147-154. 
[26] Y.-Z. Fan, Largest eigenvalue of a unicyclic mixed graph, Appl. Math. J. Chi¬nese Univ. Ser. B 19 (2004), 140-148. 
[27] Y.-Z. Fan, B.-S. Tam, J. Zhou, Maximizing spectral radius of unoriented Lapla¬cian matrix over bicyclic graphs of a given order, Linear and Multilinear Al¬gebra 56 (2008), 381-397. 
[28] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2nd ed., An¬nals Disc. Math. 57, North-Holland, Amsterdam, 2004. 
[29] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001. 
[30] P.L. Hammer, A.K. Kelmans, Laplacian spectra and spanning trees of thresh¬old graphs, Discrete Appl. Math. 65 (1996), 255-273. 
[31] Y.-P Hou, J.-S. Li and Y.-L. Pan, On the Laplacian eigenvalues of signed graphs, Linear Multilinear Algebra 51 (2003) 21-30. 
[32] R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, 1985. 
[33] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991. 
[34] R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199 (1994), 381-389. 
[35] R. Merris, Graph Theory, Wiley Interscience, 2001. 
[36] N.V.R. Mahadev, U.N. Peled,Threshold Graphs and Related Topics, Ann. Discrete Math., vol.56, North-Holland, Amsterdam, (1995). 
[37] I. Niven, H.S. Zuckerman, H.L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, John Wiley and Sons,Inc., 1991. 
[38] D.D. Olesky, Aidan Roy, P.	van den Driessche, Maximal graphs and graphs with maximal spectral radius, Linear Algebra Appl. 346(2002), 109-130. 
[39] U. N. Peled, M. K. Srinivasan, The polytope of degree sequences, Linear Al¬gebra Appl. 114-115(1989), 349-377. 
[40] P. Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl. 110 (1988) 43-53. 
[41] S.K. Simi´c, E.M. Li Marzi, F. Belardo, Connected graphs of fixed order and size with maximal index: structural consideration, Le Matematiche 59(1-2)(2004), 349-365. 
[42] Z. Stani´c, Some reconstructions in spectral graph theory and graphs with in¬tegral Q-spectrum, (Serbian), Doctoral Thesis, Faculty of Mathematics, Bel¬grade, 2007. 
[43] Z. Stani´c, There are exactly 172 connected Q-integral graphs up to 10 vertices, Novi Sad J. Math., 37 (2007),193-205. 
[44] Z. Stani´c, Some results on Q-integral graphs, Ars Combin., 90 (2009), 321-335. 
[45] D. Stevanovi´c, Research problems from the Aveiro workshop on graph spectra, Linear Algebra Appl. 423 (2007), 172-181. 
[46] B.-S. Tam, Y.-Z. Fan, J. Zhou, Unoriented Laplacian maximizing graphs are degree maximal, Linear Algebra Appl. 429(2008), 735-758. 
[47] B.-S. Tam, S.-H. Wu, On the reduced signless Laplacian spectrum of a degree maximal graph, Linear Algebra Appl. 432 (2010), 1734-1756. 
[48] H. Wolkowicz, G.P.H. Styan, Bounds for eigenvalues using traces, Linear Al¬gebra Appl. 29 (1980), 471-506. 
[49] X.-D. Zhang and J.-S. Li, The Laplacian spectrum of a mixed graph, Linear Algebra Appl. 353 (2002) 11-20. 
[50] X.-D. Zhang, R. Lou, The Laplacian eigenvalues of	a mixed graph, Linear Algebra Appl. 362 (2003) 109-119.