淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2806201023143900
中文論文名稱 簡約圖譜矩陣理論與其應用
英文論文名稱 On Reduced Graph Matrices and Their Applications
校院名稱 淡江大學
系所名稱(中) 數學學系博士班
系所名稱(英) Department of Mathematics
學年度 98
學期 2
出版年 99
研究生中文姓名 吳淑惠
研究生英文姓名 Shu-Hui Wu
學號 892150011
學位類別 博士
語文別 英文
口試日期 2010-06-19
論文頁數 108頁
口試委員 指導教授-譚必信
委員-張鎮華
委員-傅恆霖
委員-葉鴻國
委員-高金美
委員-胡守仁
委員-譚必信
中文關鍵字 極大圖  簡約無符號拉普拉斯  無符號拉普拉斯譜  特徵多項式  鄰域等價類 
英文關鍵字 Maximal graph  Reduced signless Laplacian  Signless Laplacian spectrum  Characteristic polynomial  Neighborhood equivalence class 
學科別分類
中文摘要 對一個(簡單)圖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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2010-07-26公開。
  • 同意授權瀏覽/列印電子全文服務,於2010-07-26起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信