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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2506201014563600
中文論文名稱 具有最大無符號拉普拉斯譜半徑的圖及其相關主題之研究
英文論文名稱 Graphs with maximal signless Laplacian spectral radius and related topics
校院名稱 淡江大學
系所名稱(中) 數學學系博士班
系所名稱(英) Department of Mathematics
學年度 98
學期 2
出版年 99
研究生中文姓名 張定中
研究生英文姓名 Ting-Chung Chang
電子信箱 litpao@mail.chihlee.edu.tw
學號 892150045
學位類別 博士
語文別 英文
口試日期 2010-06-19
論文頁數 131頁
口試委員 指導教授-譚必信
委員-張鎮華
委員-傅恆霖
委員-葉鴻國
委員-高金美
委員-胡守仁
中文關鍵字 無符號拉普拉斯  度極大圖  譜半徑  線圖  控制頂點  鄰域等價類  圖譜 
英文關鍵字 Signless Laplacian  Maximal graphs  Spectral radius  Line graph  Dominating vertex  Neighborhood equivalence class  Graph spectra 
學科別分類
中文摘要 對一個(簡單) 圖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)) 在圖譜理論中, 長久以來一直有個經典的問題尚未解決, 也就是決定在固定連通圖的點數為n, 邊數為n+ k 的狀況下達到最大譜半徑(ρ(A(G))) 的圖; 關於這個問題, 有學者僅對3 ≤ 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¬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)) 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.
論文目次 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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-07-09公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-07-09起公開。


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