Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10630
Title: | 星星森林的邊拉姆西數 Size Ramsey Numbers of Star Forests |
Authors: | Yen-Jen Cheng 鄭硯仁 |
Advisor: | 張鎮華(Gerard Jennhwa Chang) |
Keyword: | 拉姆西,星星森林, Ramsey,star forest, |
Publication Year : | 2010 |
Degree: | 碩士 |
Abstract: | 對於圖 G_1, G_2, ..., G_r和 F,如果當 F的邊被著上 1, 2, ..., r這些顏色時,總是存在 i使得著顏色 i的邊中包含圖 G_$的話,則記作 F -> (G_1, G_2, ..., G_r)。在所有滿足 F -> (G_1, G_2, ..., G_r)的 F中,所含邊數的最小值稱為邊拉姆西數,記作 r(G_1, G_2, ..., G_r)。
假設 G_1 = U_{i=1}^{m}{K_{1,a_i}},G_2 = U_{i=1}^{n}{K_{1, b_i}}且 a_1 >= a_2 >= ... >= a_m,b_1 >= b_2 >= ... >= b_n,令 l_s = max_{i+j=s+1}{(a_i+b_j-1)},Burr, Erdos, Faudree, Rousseau 和 Schelp [4]猜測 $r(G_1, G_2) = sum_{s=1}^{m+n-1}{l_s}。這篇論文的目的是研究這個猜想在 a_1,b_1以外的數都等於 1時的情形。 For graphs G_1, G_2, ..., G_r and F, we write F -> (G_1, G_2, ..., G_r)$ to mean that if the edges of F are colored by 1, 2, ..., r then there exists some i such that the edges of color i contains a copy of G_i. The size Ramsey number r(G_1, G_2, ..., G_r) is the least number of edges of a graph F for which F -> (G_1, G_2, ..., G_r). Suppose G_1 = U_{i=1}^{m}{K_{1,a_i}} with a_1 >= a_2 >= ... >= a_m and G_2 = U_{i=1}^{n}{K_{1, b_i}} with b_1 >= b_2 >= ... >= b_n. Let l_s = max_{i+j=s+1}{(a_i+b_j-1)}. Burr, Erdos, Faudree, Rousseau and Schelp [4] conjectured that r(G_1, G_2) = sum_{s=1}^{m+n-1}{ell_s}. The purpose of this thesis is to study the conjecture for the case when a_i = b_j = 1 for 2 <= i <= m and $2 <= j <= n. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10630 |
Fulltext Rights: | 同意授權(全球公開) |
Appears in Collections: | 數學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-99-1.pdf | 761.79 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.