一個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.

Contents
1 Introduction 1
2 Prelimilaries and Known Results 5
2.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Graph Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Characterizing 4-Regular Graphs 14
3.1 4-regular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 3-Reducible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.1 hSiG is a P3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.2 hSiG is a C3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.3 hSiG is a union of P1 and P2 . . . . . . . . . . . . . . . . . . . . . . 23
4 4-Cycle System of Kn − E(G) 50
4.1 (n, t)-admissible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Recursive Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5 Concluding Remarks 69
References 70
Appendix 75

List of Figures
Figure 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Figure 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Figure 3.1.1 Non-isomorphic 4-regular graphs of order at most 7 . . . . 15
Figure 3.1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Figure 3.1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Figure 3.1.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Figure 3.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Figure 3.2.2 G9,1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Figure 3.2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Figure 3.2.4 GS,1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Figure 3.2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Figure 3.2.6 GS,5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Figure 3.2.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Figure 3.2.8 R3,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Figure 3.2.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Figure 3.2.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Figure 3.2.11 R3,3,1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Figure 3.2.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Figure 3.2.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Figure 3.2.14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Figure 3.2.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Figure 3.2.16 R3,3,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Figure 3.2.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Figure 3.2.18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Figure 3.2.19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Figure 3.2.20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Figure 3.2.21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Figure 3.2.22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Figure 3.2.23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Figure 3.2.24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Figure 3.2.25 R3,4,1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Figure 3.2.26 R3,4,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Figure 3.2.27 R3,4,3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Figure 3.2.28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Figure 3.2.29 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Figure 3.2.30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Figure 3.2.31 R3,4,4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Figure 3.2.32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Figure 3.2.33 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Figure 3.2.34 R3,4,5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Figure 3.2.35 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Figure 3.2.36 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Figure 3.2.37 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Figure 3.2.38 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Figure 3.2.39 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Figure 3.2.40 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Figure 3.2.41 R3,4,6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Figure 3.2.42 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Figure 3.2.43 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Figure 3.2.44 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Figure 3.2.45 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Figure 3.2.46 R3,4,7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Figure 3.2.47 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Figure 3.2.48 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Figure 3.2.49 R3,5,1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Figure 3.2.50 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Figure 3.2.51 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Figure 3.2.52 R3,5,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Figure 3.2.53 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Figure 3.2.54 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Figure 3.2.55 R3,5,3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Figure 3.2.56 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Figure 3.2.57 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Figure 3.2.58 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Figure 3.2.59 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Figure 3.2.60 R3,5,4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Figure 3.2.61 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Figure 3.2.62 R3,6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Figure 3.2.63 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Figure 3.2.64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Figure 4.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Figure 4.3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Figure 4.3.2 G8,5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Figure 4.3.3 GS and H . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Figure 4.3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

List of Tables
Table 3.1 Number of non-isomorphic connected 4-regular graphs . . . . 15

[1] P. Adams, D. Bryant and A. Khodkar, 3, 5-cycle decompositions, J. Combin. Des., 6 (1998) 91-110.
[2] P. Adams, D. Bryant and A. Khodkar, On Alspach’s conjecture with two even cycle lengths, Discrete Math., 223 (2000) 1-12.
[3] B. Alspach, Research problems, problem 3, Discrete Math., 36 (1981) 333-334.
[4] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl., 52 (2008) 7-20.
[5] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn−I, J. Combin. Theory B, 81 (2001) 77-99.
[6] B. Alspach and S. Marshall, Evan cycle decompositions of complete graphs minus a 1-factor, J. Combin. Des., 2 (1991) 441-458.
[7] D. J. Ashe, H. L. Fu and C. A. Rodger, A solution to the forest leave problem for partial 6-cycle systems, Discrete Math., 281 (2004) 27-41.
[8] D. J. Ashe, H. L. Fu and C. A. Rodger, All 2-regular leaves of partial 6-cycle systems, Ars Combin., 76 (2005) 129-150.
[9] P. N. Balister, On Alspach conjecture, Combin. Probab. Comput., 10 (2001) 95-125.
[10] Zs. Baranyai, On the factorization of the complete uniform hypergraph, Infinite and finite sets (Colloq., Keszthely, 1973), Vol. I, pp. 91-108. Colloq. Math. Soc.
Janos Bolyai 10, North-Holland, Amsterdam, 1975.
[11] D. Bryant, Cycle decompositions of complete graphs, in Surveys in Combinatorics,2007, A. Hilton and J. Talbot (Editors), London Mathematical Society Lecture
Note Series 346, Proceedings of the 21st British Combinatorial Conference, Cambridge University Press, 2007 67-97.
[12] D. Bryant, Hamilton cycle rich two-factorizations of complete graphs, J. Combin. Design, 12(2) (2004) 147-155.
[13] D. Bryant, Y. Chang, C. A. Rodger and R. Wei, Two-dimensional balanced sampling plans excluding contiguous units, Comm. Statist. Theory Methods, 31 (2002)
1441-1455.
[14] D. Bryant and D. Horsley, Decompositions of complete graphs into long cycles, Bull. London Math. Soc., 41 (2009) 927-934.
[15] D. Bryant and D. Horsley, An asymptotic solution to the cycle deocmposition problem for complete graphs, J. Combin. Theory A, 117 (2010) 1258-1284.
[16] D. Bryant, D. Horsley and W. Pettersson, Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, arXiv:1204.3709v2 [math.CO], (2013).
[17] D. Bryant, A. Khodkar and H. L. Fu, (m, n)-cycle systems, J. Statist. Plann. Inference, 74 (1998) 365-370.
[18] D. Bryant and B. Maenhaut, Decompositions of complete graphs into triangles and Hamilton cycles, J. Combin. Des., 12 (2004) 221-232.
[19] D. Bryant and C. A. Rodger, Cycle decompositions, in The CRC Handbook of Combinatorial Designs, 2nd edition (Eds. C. J. Colbourn, J. H. Dinitz), CRC Press,
Boca Raton, 2007 pp. 373-382.
[20] H. Buchanan II, Graph factors and hamiltonian decompositions, Ph.D. Dissertation,West Virginia University, 1997.
[21] C. J. Colbourn and A. Rosa, Quadratic leaves of maximal partial triple systems, Graphs Combin., 2(1986) 317-337.
[22] G. A. Dirac, Some theorems on abstract graphs, Proceedings of the London Mathematical Society, 3 (1952) 69-81.
[23] C. M. Fu, H. L. Fu, C. A. Rodger and Todd Smith, All graphs with maximum degree three whose completements have 4-cycle decompositions, Discrete Math., 308 (2008) 2901-2909.
[24] H. L. Fu and C. A. Rodger, Forest leaves and four-cycles, J. Graph Theory, 33 (2000) 161-166.
[25] H. L. Fu and C. A. Rodger, Four-cycle system with two-regular Leaves, Graphs and Combin., 17 (2001) 457-461.
[26] R. H‥aggkvist, A lemma on cycle decompositions, Ann. Discrete Math., 27 (1985) 227-232.
[27] A. S. Hedayat, C. R. Rao and J. Stufken, Sampling plans excluding contiguous units, J. Statist. Plann. Inference, 19 (1988) 159-170.
[28] K. Heinrich, P. Hor′ak and A. Rosa, On Alspach’s conjecture, Discrete Math., 77 (1989) 97-121.
[29] C. J. Colbourn, C. C. Lindner and C. A. Rodger, Neighbor designs and m-wheel systems, J. Statist. Plann. Inference, 27 (1991) 335-340.
[30] H. Jordon, Alspach’s Problem: The case of Hamilton cycles and 5-cycles, Electron. J. Combin., 18 (2011) 82-100.
[31] T. P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. J., 2 (1847) 191-204.
[32] A. Kotzig, On decomposition of the complete graph into 4k-gons, Mat.-Fyz. Cas., 15 (1965) 227-233.
[33] C. C. Lindner and C. A. Rodger, em Decomposition into Cycles II: Cycle Systems, Contemporary Design Theory, Wiley-Interscience Series Discrete Mathematics Optimization,
Wiley, New York, 1992 pp. 325-369.
[34] E. Lucas, ”R′ecreations Math′ematiqu′es,” Vol II, Gauthier-Villars, Paris, (1892).
[35] R. C. Read and R. J. Wilson, An Atlas of graphs, Plarendon Press · Oxford (1998).
[36] D. H. Rees, Some designs of use in serology, Biometrics, 23 (1967) 779-791.
[37] C. A. Rodger, in: C. J. Colbourn and J. H. Dinitz (Eds.), Cycle Systems, The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL, 1996 pp. 266-
269.
[38] C. A. Rodger, Hamilton decomposable graphs with specified leaves, Graphs Combin. 20 (2004) 541-543.
[39] A. Rosa, On cyclic decompositions of the complete graph into 4m+2-gons, Mat.-Fyz. Cas., 16 (1966) 349-352.
[40] A. Rosa, On the cyclic decompositions of the complete graph into polygons with an odd number of edges, Casopis Pest. Math., 91 (1966) 53-63.
[41] M. ˇ Sajna, Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Des., 10 (2002) 27-78.
[42] J. Sch‥onheim an A. Bialostochi, Packing and covering of the complete graph with4-cycles, Canad. Math. Bull., 18 (1975) 703-708.
[43] D. Sotteau, Decomposition of Km,n(Km,n) into cycles (circuits) of length 2k, J. Combin. Theory B 30 (1981) 75.81.