對一個(簡單)圖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.針對已知的極大圖的拉普拉斯的譜的描述，給予另一種新證明。

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.

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

[1] 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.
[2] 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.
[3] F. Boesch, C. Suffel, R. Tindell, The neighborhood inclusion structure of a graph, Math. Comput. Modelling 17 (1993), 25-28.
[4] R.A. Brualdi, H.J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1991.
[5] T.-C. Chang, B.-S. Tam, Graphs with maximal signless Laplacian spectral radius, Linear Algebra Appl. 432 (2010), 1708-1733.
[6] T.-C. Chang, B.-S. Tam, S.-H. Wu, Theorems on partitioned matrices revisited and their applications to study of graph spectra, submitted for publication.
[7] D. Cvetkovi´c, M. Doob, H. Sachs, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.
[8] D. Cvetkovic, P. Rowlinson, On connected graphs with maximal index, Publ. Inst. Math. (Beograd) 39 (53) (1986) 45-54.
[9] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Eigenspaces of graphs, Cambridge University Press, Cambridge, 1997.
[10] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Spectral generalizations of line graphs:on graphs with least eigenvalue 2, Cambridge University Press, Cambridge,2004.
[11] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007), 155-171.
[12] D. Cvetkovi´c, P. Rowlinson, S. Simi´c, Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math. (Beograd)(N.S.), 81(95) (2007), 11-27. 
[13] D. Cvetkovi´c, S.K. Simi´c, Towards a spectral theory of graphs based on thesignless Laplacian I, Publ. Inst. Math. (Beograd), 81(99)(2009), 19-33.
[14] 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.
[15] 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. 
[16] K.C. Das, Sharp lower bounds on the Laplacian eigenvalues of trees, Linear Algebra Appl. 384 (2004), 155-169.
[17] K.C. Das, The Laplacian spectrum of a graph, Computers & Math. Appl. 48 (2004), 715-724.
[18] K.C. Das, On conjectures involving second largest signless Laplacian eigenvalue of graphs, Linear Algebra Appl., to appear.
[19] E.R. van Dam, W. Haemers, Which graphs are determined by their spectrum ? Linear Algebra Appl. 373 (2003), 241-272.
[20] Y.-Z. Fan, Largest eigenvalue of a unicyclic mixed graph, Appl. Math. J. Chinese Univ. Ser. B 19 (2004), 140-148.
[21] Y.-Z. Fan, B.-S. Tam, J. Zhou, Maximizing spectral radius of unoriented Laplacian matrix over bicyclic graphs of a given order, Linear and Multilinear Algebra 56(2008), 381-397.
[22] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001.
[23] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Ann. Discrete Math., vol. 57, second ed., North-Holland, Amsterdam, 2004.
[24] L. S. Goddard, H. Schneider, Matrices with a nonzero commutator, Proc. Cambridge Phil. Soc. 51 (1955), 551-553.
[25] R. Grone, R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math. 7 (1994), 221-229.
[26] W.H. Haemers, Eigenvalue Techniques in Design and Graph Theory, Math. Centre Tract 121, Mathematical Centre, Amsterdam, 1980.
[27] W.H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 227-228(1995), 593-616. 
[28] P.L. Hammer, T. Ibaraki and B. Simeone, Threshold sequences, SIAM J. Algebraic Discrete Methods 2 (1981), 39-49.
[29] P.L. Hammer, A.K. Kelmans, Laplacian spectra and spanning trees of threshold graphs, Discrete Appl. Math. 65 (1996), 255-273. 
[30] P.L. Hammer, A.K. Kelmans, Laplacian spectra and spanning trees of threshold graphs, Discrete Appl. Math. 65 (1996), 255-273.
[31] E.V. Haynsworth, Applications of a theorem on partitioned matrices, J. Res.Nat. Bureau Stand. 62B (1959), 73-78.
[32] E.V. Haynsworth, A reduction formula for partitioned matrices, J. Res. Nat. Bureau Stand. 64B (1960), 171-174.
[33] R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, 1985.
[34] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991.
[35] Y.-P. Hou, J.-S. Li, Y.-L. Pan, On the Laplacian eigenvalues of signed graphs, Linear and Multilinear Algebra 51 (2003) 21-30.
[36] N.V.R. Mahadev, U.N. Peled, Threshold Graphs and Related Topics, Ann. Dis- crete Math., Vol. 56, North-Holland, Amsterdam, 1995.
[37] R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199(1994) 381-389. 
[38] R. Merris, Graph Theory, Wiley Interscience, 2001.
[39] D.D. Olesky, A. Roy, P. van den Driessche, Maximal graphs and graphs with maximal spectral radius, Linear Algebra Appl. 346(2002) 109-130. 
[40] M. Petersdorf, H. Sachs, ¨Uber Spektrum, Automorphismengruppe und Teiler eines Graphen, Wiss. Z., T.H. Ilmenau, 15 (1969), 123-128.
[41] P. Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl. 110 (1988) 43-53. 
[42] 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.
[43] T. Stephen, A majorization bound for the eigenvalues of some graph Laplacians, SIAM J. Discrete Math. 21 (2007), 303-312.
[44] D. Stevanovi´c, Research problems from the Aveiro workshop on graph spectra, Linear Algebra Appl. 423 (2007), 172-181. 
[45] B.-S. Tam, On the distinguished eigenvalues of a cone-preserving map, Linear Algebra Appl. 131 (1990), 17-37.
[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] X.-D. Zhang, J.-S. Li, The Laplacian spectrum of a mixed graph, Linear Algebra Appl. 353 (2002) 11-20.