教師資料查詢 | 類別: 期刊論文 | 教師: 譚必信 Tam Bit-shun (瀏覽個人網頁)

標題:Unoriented Laplacian maximizing graphs are degree maximal
學年97
學期1
出版(發表)日期2008/08/01
作品名稱Unoriented Laplacian maximizing graphs are degree maximal
作品名稱(其他語言)
著者譚必信; Tam, Bit-shun; Fan, Yi-zheng; Zhou, Jun
單位淡江大學數學學系
出版者Philadelphia: Elsevier Inc.
著錄名稱、卷期、頁數Linear Algebra and its Applications 429(4), pp.735-758
摘要A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices it, v of G, the sets N(u) \ {v}, N(v) \ {u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed. (C) 2008 Elsevier Inc. All rights reserved.
關鍵字unoriented Laplacian matrix; spectral radius; perron vector; maximizing; maximal graph; threshold graph; degree sequence; vicinal pre-order
語言英文
ISSN0024-3795
期刊性質國外
收錄於SCI
產學合作
通訊作者
審稿制度
國別美國
公開徵稿
出版型式
相關連結
Google+ 推薦功能,讓全世界都能看到您的推薦!