Packing graphs with 4-cycles

機構典藏 > College of Sciences > Department of Applied Mathematics and Data Science > Thesis > Item 987654321/94023

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

Title:	Packing graphs with 4-cycles
Other Titles:	4-迴圈裝填圖的探討
Authors:	徐育鋒;Hsu, Yu-Fong
Contributors:	淡江大學數學學系博士班高金美;Kau Fu, Chin-Mei
Keywords:	完全圖;裝填;4-迴圈系統;4-正則圖;complete graph;packing;4-cycle system;4-regular graph
Date:	2013
Issue Date:	2014-01-23 13:48:17 (UTC+8)
Abstract:	一個n個點的完全圖是一個任兩點皆相鄰的簡單圖，記作Kn。一個n個點的迴圈稱為n-迴圈且記作(v1, v2, …, vn)，其中v1, v2, …, vn為迴圈的點且v1v2, v2v3, …, vn−1vn, vnv1為迴圈的邊。一個4-正則圖是一個每一點度數皆為4的圖。假如G是Kn的子圖，則Kn –E(G)是一個將Kn中所有圖G的邊皆移除的圖。假如C是圖Q的一個k-迴圈系統，則C是一個蒐集Q中邊互斥的k-迴圈之集合且Q中的每一邊只會出現在C中唯一的一個k-迴圈中，也就是說，Q 可以被分割成k-迴圈。在本篇論文中，我們得到下列結果： (1) 幾乎所有點數至少為8的4-正則圖皆為3-可縮減。 (2) 令G是一個t個點的4-正則圖。 (i) 假如G是一個由t個點互斥的K5所組成且G是(n,5t)-可容許，則當n ≡ 1，5 (mod 8)時，Kn – E(G)存在一個4-迴圈系統。 (ii) 假如G是(n,t)-可容許且n ≥ (4t – 5)/3，則當n ≡ 1, 5 (mod 8)時，Kn – E(G)存在一個4-迴圈系統，除了K9 – E(G)，其中G跟兩個點數為8的4-正則圖同構。關鍵字：完全圖，裝填，4-迴圈系統，4-正則圖。 A complete graph with n vertices is a simple graph whose vertices are pairwise adjacent, denoted by Kn. A cycle with n vertices is called an n-cycle and is denoted (v1, v2, …, vn), where v1, v2, …, vn are the vertices of the cycle and v1v2, v2v3, …, vn−1vn, vnv1 are the edges. A 4-regular graph is a graph whose degree of each vertex is 4. If G is a subgraph of Kn, then Kn –E(G) is the graph by removing all edges of G from Kn. If C is a k-cycle system of a graph Q, then C is the set of edge-disjoint k-cycles in Q and each edge of Q occurs in exactly one of k-cycles in C, i.e., Q can be decomposed into k-cycles. In this thesis, we obtain the following results: (1) Almost all 4-regular graphs of order at least 8 are 3-reducible. (2) Let G be a 4-regular graph of order t. (i) If G is a vertex-disjoint union of t copies of K5 and G is (n,5t)-admissible, then there exists a 4-cycle system of Kn – E(G) for n ≡ 1, 5 (mod 8). (ii) If G is (n,t)-admissible and n ≥ (4t − 5)/3, then there exists a 4-cycle system of Kn – E(G), for n ≡ 1, 5 (mod 8), except that K9 – E(G), where G is isomorphic to two 4-regular graphs of order 8.
Appears in Collections:	[Department of Applied Mathematics and Data Science] Thesis

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	386	View/Open

Loading...