Packing Graphs with 4-Cycles
| Autor: | Yu-Fong Hsu, 徐育鋒 |
|---|---|
| Rok vydání: | 2013 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 101 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|