English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 62797/95867 (66%)
造訪人次 : 3731043      線上人數 : 624
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
搜尋範圍 查詢小技巧:
  • 您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
  • 進階搜尋
    請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/51872


    題名: Graphs with maximal signless laplacian spectral radius and related topics
    其他題名: 具有最大無符號拉普拉斯譜半徑的圖及其相關主題之研究
    作者: 張定中;Chang, Ting-chung
    貢獻者: 淡江大學數學學系博士班
    譚必信
    關鍵詞: 無符號拉普拉斯;度極大圖;譜半徑;線圖;控制頂點;鄰域等價類;圖譜;Signless Laplacian;Maximal graphs;Spectral radius;Line graph;Dominating vertex;Neighborhood equivalence class;Graph spectra
    日期: 2010
    上傳時間: 2010-09-23 16:13:57 (UTC+8)
    摘要: 對一個(簡單) 圖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¬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.
    顯示於類別:[數學學系暨研究所] 學位論文

    文件中的檔案:

    檔案 大小格式瀏覽次數
    index.html0KbHTML344檢視/開啟

    在機構典藏中所有的資料項目都受到原著作權保護.

    TAIR相關文章

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - 回饋