完全雙分圖之星林分解數的探討

機構典藏 > College of Sciences > Graduate Institute & Department of Mathematics > Thesis > Item 987654321/32916

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/32916

Title:	完全雙分圖之星林分解數的探討
Other Titles:	The study of the star arboricity of complete bipartite graphs
Authors:	廖藝淳;Liao, Yi-chun
Contributors:	淡江大學數學學系碩士班高金美;Kau, Chin-mei
Keywords:	完全二分圖;星圖;星林圖;分割;星林分解數;complete bipartite graph;star;star forest;decomposition;star arboricity
Date:	2006
Issue Date:	2010-01-11 02:58:19 (UTC+8)
Abstract:	假設V1﹐V2為兩個集合﹐若V＝V1∪V2﹐V1∩V2＝Φ且E＝{uv︱u V1, v V2}﹐則稱(V, E)為完全二分圖。若︱V1︱＝m﹐︱V2︱＝n﹐則此完全二分圖記為Km,n。當︱V1︱＝1﹐︱V2︱＝n﹐稱K1,n為星圖﹙Star﹚。當圖G的每一個最大連通子圖都是星圖時﹐我們稱圖G為星林圖﹙Star-forest﹚。將圖G分割成邊相異之星林圖時﹐其最少星林圖的個數稱為G的星林分解數﹐用(G)表示。在本論文中﹐我們考慮的是完全二分圖K2n,2n+4﹐n≧3的星林分解數﹐首先我們將Egawa等在論文中所証之結果重新給予完整的証明﹐而獲得下面的結果: (1)(K5,5)=4 (2)(K5,6)=5 (3)(K6,6)=5 (4)(K6,8)=5 (5)(K6,10)=6。進而推廣獲得(K2n,2n+4)=n+3﹐n≧3。 Let V1 and V2 be two set. If V＝V1∪V2﹐V1∩V2＝Φ, and E＝{uv︱u V1, v V2}﹐then we call (V,E) is a complete bipartite graph. If \|V1\| = m and \|V2\| = n, then this complete bipartite graph is denoted by Km,n. If \|V1\| = 1 and \|V2\| = n, then we call K1,n is a star. If every component of the graph G is a star, then we call G is a star forest. If G can be decomposed into star forests, we call the minimum number of star forests in the decomposition of G is the star arboricity of G, denoted by (G). In this thesis, we consider the star arboricity of complete bipartite graph K2n,2n+4, as n≧3. First, we review the proof in the paper of Egawa et al. We get the following results: (1)(K5,5)=4 (2)(K5,6)=5 (3)(K6,6)=5 (4)(K6,8)=5 (5)(K6,10)=6. Then we improve the result (K2n,2n+4)=n+3﹐n≧3, and give the proof.
Appears in Collections:	[Graduate Institute & Department of Mathematics] Thesis

Files in This Item:

File	Size	Format
	0Kb	Unknown	305	View/Open

Loading...