請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34027
標題: | 關於短腳蜘蛛圖的Erdös-Sós猜想 The Erdös-Sós Conjecture for Short-leg Spiders |
作者: | Chun-Ting Lee 李俊廷 |
指導教授: | 張鎮華 |
關鍵字: | 蜘蛛圖,Erd&ouml,s-S&oacute,s猜想, spiders,Erd&ouml,s-S&oacute,s conjecture, |
出版年 : | 2006 |
學位: | 碩士 |
摘要: | 圖論中有關極值理論的 Erdos-Gallai 定理: n 個頂點的圖如果包含超過 (k-1)n/2 個邊,則其必包含一個 k 邊的路。根據這項結論, Erdos以及 Sos 猜測在相同的條件下,這樣的圖將會包含任何一個 k 邊的樹。蜘蛛圖,一種特別的樹,最多只能有一個頂點的度超過 2,這樣的頂點我們稱之為中心,其他的頂點的度為 1 或 2。一條從中心到度為 1 的頂點之路稱為蜘蛛圖的一隻腳。因此,
一條路即為一個一隻腳或兩隻腳的蜘蛛圖。在這篇論文中,我們將證明如果一 n 點的圖有超過 (k-1)n/2 個邊,那麼他將包含所有一隻腳長度為 5,其餘的腳長度都是 5 以下的 k 邊蜘蛛圖。另外,我們也證明如果一個 n 點的圖有超過 (k-1)n/2 個邊,且他有漢米爾頓圈,則其必包含任何 k 邊的蜘蛛圖。 A classical result on extremal graph theory is the Erd˝os-Gallai Theorem: if a graph with n vertices has more than (k−1)n/2 edges, then it contains a path of k edges. Motivated by the result, Erd˝os and S´os conjectured that under the same condition, the graph should contain every tree of k edges. A spider is a tree in which each vertex has degree 1 or 2, except for possibly one vertex, called the center of the spider. A leg of a spider is a path from the center to a vertex of degree one. Thus, a path is a spider of 1 or 2 legs. In this thesis, we prove that if a graph with n vertices has more than (k−1)n/2 edges, then it contains every k-edge spider whose legs are of length at most 4 except exactly one is of length 5. In addition, we also prove that a Hamiltonian graph with n vertices and more than (k−1)n/2 edges contains every spider of k edges. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/34027 |
全文授權: | 有償授權 |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 226.06 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。