| 摘要: | 一個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. |
