完全圖分割成4-迴圈太陽圖之探討

淡江大學機構典藏 > 理學院 > 應用數學與數據科學學系 > 學位論文 > Item 987654321/32900

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

Title:	完全圖分割成4-迴圈太陽圖之探討
Other Titles:	The decomposition of complete graphs into sun graphs of 4-cycle
Authors:	邱群博;Ciou, Cyun-bo
Contributors:	淡江大學數學學系碩士班高金美;Kau, Chin-mei
Keywords:	完全二分圖;完全圖;4-迴圈;太陽圖;分解;complete bipartite graph;complete graph;4-cycle;sun graph;decomposition
Date:	2008
Issue Date:	2010-01-11 02:56:55 (UTC+8)
Abstract:	當一個含有n個點的圖中，任兩點都有邊相連，我們稱此圖為完全圖，記為K_(n)。當一個圖中的點集合可以分成兩個非空的集合V_(1)及V_(2)，若 V_(1)中的每一點都與V_(2)中的點有邊相連，且在V_(1)及V_(2)中的點都沒有邊相連，則稱此圖為完全二分圖；若 V_(1)中有m個點，V_(2)中有n個點，則此完全二分圖記為K_(m,n)。假設 v_(1), v_(2), v_(3), v_(4)為4-迴圈C_(4)的依序四個頂點，在 C_(4)外面加入4個點w_(1), w_(2), w_(3), w_(4)及4條邊 {v_(i), w_(i) }, 1≦ i≦ 4，所形成的圖稱為C_(4)的太陽圖，記為S(C_(4))。在本篇論文中，我們證明了 (1) 當m≧ n≧ 4, n≠ 5, 且若n= 4則m不為4k+2形態時，完全二分圖K_(m,n)能分割成4-迴圈太陽圖的充分必要條件為m×n為8的倍數，(2) 完全圖K_(n)能分割成4-迴圈太陽圖的充分必要條件為n≡ 0 或1 (mod 16)。 A graph with n vertices satisfies that every two vertices are connected by an edge, then we call this graph a complete graph with n vertices, denoted by K_(n). If the vertex set of a graph can be partitioned into two disjoint nonempty sets V_(1) and V_(2) , every vertex in V_(1) connects every vertex in V_(2) and there is no edge in V_(1) and V_(2), then we call this graph is a complete bipartite graph. If V_(1) contains m elements and V_(2) contains n elements, then we denote this complete bipartite graph K_(m,n). Let {v_(1), v_(2), v_(3), v_(4)} be the vertex set of a 4-cycle C_(4). If we add another four vertices w_(1), w_(2), w_(3), w_(4) and four edges {v_(i), w_(i)}, 1≦ i≦ 4 to C_(4), then we call this graph a sun graph of C_(4), denoted by S(C_(4)). In this thesis, we proved that (1) if m≧ n≧ 4, n≠ 5, and if n= 4 then m is not the form of 4k+2, the complete bipartite graph K_(n,m) can be decomposed into sun graphs of 4-cycle (S(C_(4))) if and only if mn is a multiple of 8, and (2) the complete graph K_(n) can be decomposed into sun graphs of 4-cycle (S(C_(4))) if and only if n≡ 0, 1 (mod 16).
Appears in Collections:	[應用數學與數據科學學系] 學位論文

Files in This Item:

File	Size	Format
	0Kb	Unknown	284	View/Open

Loading...