圖形的路徑分解,迴路分解和星形分解; Path, Cycle and Star Decompositions of Graphs

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/7824

Title:	圖形的路徑分解,迴路分解和星形分解;Path, Cycle and Star Decompositions of Graphs
Authors:	李明茹;Ming-Ju Lee
Contributors:	數學研究所
Date:	2007-06-22
Issue Date:	2009-09-22 11:06:24 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	圖形分解是圖形理論中的一個非常重要的主題，因為許多數學結構與圖形分解有相當緊密的聯結，而且圖形分解的結果可以廣泛的應用到其他的領域。因子分解(factorization)是一種特殊型態的圖形分解，其與組合設計(combinatorial design)有密不可分的關係。我們有許多類型的分解問題，例如星型分解(star decomposition)、路徑分解 (path decomposition)、迴路分解(cycle decomposition)、完全二部圖分解(complete bipartite decomposition)等等。直到今日，上述分解依然是熱門討論話題。在本篇論文中，某些有向圖的反向迴路(antidirected cycle)分解和有向路徑分解與某些圖形的毛毛蟲因子分解(caterpillar factorization)的問題將被探討。圖形分解與圖形的蔭度(arboricity) 有著多樣且緊密的關係。本論文，我們同時會討論某些圖形的線性蔭度 (linear arboricity)與星形蔭度(star arboricity)。本論文將分為七個章節來做探討。第一章將介紹基本的定義與符號。第二章為探討圖形的路徑分解。首先，我們為完全三部多重邊圖的同構路徑分解給定一個充分必要條件。接著探討完全三部多重有向邊圖的同構有向路徑分解。第三章將對完全對稱圖形的反向迴路分解的存在給定一個充分必要條件。第四章將對完全對稱圖形減去一因子 (one-factor)的反向迴路分解的存在給定一個充分必要條件。第五章將討論皇冠圖(crown)中毛毛蟲的因子分解。首先給予在皇冠圖中均衡的毛毛蟲因子分解一個充分必要條件。接著再給予在對稱皇冠圖中，有向毛毛蟲因子分解的充分必要條件。第六章，首先考慮皇冠圖的星形蔭度問題。先給定一個下界。接著探討在某些特定皇冠圖的星形蔭度。第七章，我們考慮在某些特定k當中，完全圖的長度為k的線性蔭度(linear k-arboricity)問題。 Graph decomposition is an important subject of graph theory since many mathematical structures are linked to it and its result can be widely applied in other fields. The factorization is a special type of graph decomposition, and it has close connections to combinatorial designs. There are various decomposition problems such as clique decomposition, star decomposition, path decomposition, cycle decomposition, complete bipartite decomposition, and so on. Nowadays, they continue to be popular topics of research. In this thesis, the problems of antidirected cycle decomposition and directed path decomposition of some digraph, and that of caterpillar factorization of some graphs are investigated. There are various close connections between graph decomposition and the arboricity of a graph. In this thesis, we also show that the linear arboricity and the star arboricity of some graphs. There are seven chapters in this thesis. In Chapter 1, some basic definitions and notations are introduced. In Chapter 2, we first establish a necessary and sufficient condition for the isomorphic path decomposition of complete tripari tite multigraphs. We then investigate the isomorphic directed path decomposition of complete tripartite multidigraphs. In Chapter 3, we give a necessary and sufficient condition for the existence of the antidirected cycle decompositions of complete symmetric graphs. In Chapter 4, we give a necessary and sufficient condition for the existence of the antidirected cycle decompositions of complete symmetric graphs minus a one-factor. In Chapter 5, the caterpillar factorization of crowns are studied. We first establish a necessary and sufficient condition for the balanced caterpillar factorization of crowns. Then we give a necessary and sufficient condition for the directed caterpillar factorization of symmetric crowns. In Chapter 6, we first consider the problem of the star arboricity of crowns. A lower bound is given. Then we investigate the star arboricity of some special crowns. In Chapter 7, we consider the problem of the linear k-arboricity of complete graph Kn for some specific k.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...