| 姓名 |
許立成(Li-Cheng Hsu)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
(On the Spectrum of Trees)
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
在1984年，Godsil 定義了 Bethe樹圖B(k,n)，並求出其譜半徑
ho的上界滿足 $rho<2sqrt{k}$。在我們這篇論文中，我們找出Bethe樹圖的譜，利用此結論，我們又證明了任一樹圖T 的譜半徑滿足
$$sqrt{Delta}leq
ho< min{2sqrt{Delta-1}cos{(frac{pi}{D+2})},2sqrt{Delta}cos{(frac{pi}{r+2})}},$$
其中D，r，Delta分別為此樹圖的直徑，半徑，與最大度數。此下界等號成立只發生在當T為完全二部圖K_{1,Delta}時。
|
| 摘要(英) |
In 1984, Godsil defined the Bethe tree $B(k,n)$ and showed the spectral radius $
ho$ of $B(k,n)$ satisfies $
ho<2sqrt{k}$.
In this thesis, we find the spectrum of $B(k,n)$. With this spectrum, we also show the spectral radius $
ho$ of a tree $T$ satisfies
$$sqrt{Delta}leq
ho< min{2sqrt{Delta-1}cos{(frac{pi}{D+2})},2sqrt{Delta}cos{(frac{pi}{r+2})}},$$
where $D$,$r$,$Delta$ are the diameter, radius, and the maximum degree of $T$ respectively. The equality of lower bound holds only when $T=K_{1,Delta}$.
|
| 關鍵字(中) |
★ Bethe樹 |
關鍵字(英) |
★ $v$-symmetric eigenvector
★ symmetric eigenvector
★ skew symmetric vector
★ symmetric vector
★ $i$-level subtree of Bkn
★ Bethe tree
★ $i$-level set |
| 論文目次 |
Contents
1 Historical Review and Overview of this thesis 1
1.1 Historical Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Basic Definitions of Graph Theory 4
3 Some Preliminaries on Eigenvalues of Graphs 7
3.1 The eigenvalues of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Equitable partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 The Spectrum of the Bethe Tree B(k, n) 12
4.1 Basic definitions and properties of Bethe tree . . . . . . . . . . . . . . . . . . 12
4.1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1.2 Spectrum of B(1, n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Equitable partition and symmetric eigenvector of B(k, n) . . . . . . . . . . . 16
4.2.1 An equitable partition of B(k, n) . . . . . . . . . . . . . . . . . . . . . 16
4.2.2 Symmetric eigenvectors of B(k, n) . . . . . . . . . . . . . . . . . . . . 18
4.3 v-symmetric eigenvector of B(k, n) . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Spectrum of B(k, n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Spectral radius of Trees 22
5.1 Lower bound of the spectral radius of trees . . . . . . . . . . . . . . . . . . . 22
5.2 Upper bound of the spectral radius of trees . . . . . . . . . . . . . . . . . . . 24
5.3 Possible future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Bibliography 26
|
| 參考文獻 |
[1] L. Collatz, U. Sinogowitz, Spektren Endlicher Grafen, Abh. Math. Sem. Univ. Hamburg
21 (1957) 63-77.
[2] R.A. Brualdi, A.J. HoIman, On the spectral radius of a (0;1) matrix, Linear Algebra
Appl. 65 (1985) 133-146.
[3] R.P. Stanley, A bound on the spectral radius of graphs with e edges, Linear Algebra
Appl. 67 (1987) 267-269.
[4] Y. Hong, A bound on the spectral radius of graphs, Linear Algebra Appl. 108 (1988)
135-140.
[5] D. Stevanovic, Bounding the largest eigenvalue of tree in terms of the largest vertex
degree, Linear Algebra Appl. 360 (2003) 35-42.
[6] C.D.Godsil, Spectra of trees, Ann. Disc. Math. 20(1984) 151-159.
[7] Y. Hong, J.-L. Shu, K. Fang, A sharp upper bound of the spectral radius of graphs, J.
Combin. Theory Ser. B 81 (2001) 177-183.
[8] A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin.
Theory Ser. B 83 (2001) 233-240.
[9] S. Hu, The largest eigenvalue of unicyclic graphs, Discrete Mathematics 307(2007) 280-
284.
[10] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ (2001).
|
| 指導教授 |
黃華民(Hua-Min Huang)
|
審核日期 |
2009-7-23 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
