臺灣博碩士論文加值系統

論文提要內容：
若一個圖具有n個點，並滿足其中任兩點之間，必恰有一條邊使其相連接，則稱此圖為n點完全圖，記為Kn。一個完全n分圖 是指一個圖的點可以分成n個部份，各部份分別具有m1,m2, … 及mn個點，任意兩個不同部份的點之間必恰有一條邊使其相連接，相同部份的任意兩個點之間必無邊存在。若每部份恰有m個點，其簡寫為Kn(m)。λKn(m)是指Kn(m)中的每一邊均重複λ次。圖Ｇ對三角形的裝填是指一個有序三元組 (S,H,L)，其中Ｓ為圖Ｇ的點集合﹔Ｈ是圖Ｇ中邊不重複三角形所成的集合﹔Ｌ則是Ｇ中所有不出現在Ｈ中任一三角形的邊所成的集合。我們稱Ｌ為Ｇ對三角形經由Ｈ裝填後的殘留。若Ｈ中元素個數為最多，或相當於Ｌ的元素個數為最少，此情形稱為對三角形的最大裝填，Ｌ則為最小殘留。在此篇論文中我們獲得當λ,n為整數; λ>1,n>2時，λKn對三角形的最大裝填及最小殘留。並利用λKn對三角形的最大裝填探討λKn(m)分割為最多迴圈的情形。

Abstract :
A graph is to be a complete graph Kn if the graph has n points and there is an edge joining any two points. A complete n-partite graph is a graph with n partite sets,m1,m2,….,mn points, respectively. There is an edge joining any two points which belong to different parts, and no edge connected any two points in the same part. If each part has the same number of points, say m, can be denoted by Kn(m). λKn(m) is a λ-fold complete n-partite graph, each part has m points.
A packing of G with triangles is an ordered triple (S,H,L),where S is the vertex set of G. H is a collection of edge-disjoint triangles of G and L is the set of edges in G which do not belong to any triangle of H. The set of edges in L is called the leave of the packing H of G.
If the number of elements in H is as large as possible, or equivalently the number of elements in L is as small as possible then the packing of G with triangles is said to be maximum, and L is a minimum leave.
In this thesis, we obtain the maximum packing and the minimum leave of lKn with triangles for λ,n are integers and λ>1, n>2. By using the results of the maximum packing of lKn with triangles, we try to decompose λKn(m) into most cycles.

目錄
1. 第一章 緒論………………………………………1
2. 第二章 定義及引用定理…………………………3
3. 第三章 λKn對3-邊迴圈的最大裝填……………7
4. 第四章 λKn(m)分割為最多的迴圈……………25
5.參考文獻……………………………………………37

參考文獻
[1] E.J. Billington, Decomposing complete tripartite graphs into cycles of length 3 and 4, Discrete Math 197/198 (1999), 123-135.
[2] N.J. Cavenagh and E.J. Billington, Decompositions of complete multipartite graphs into cycles of even length, Graphs Combin (to appear).
[3] C.J. Colbourn, D.G. Hoffman, and R. Rees, A new class of group divisible designs with block size three, J Combin Theory (Series A), 59 (1992), 73-89.
[4] D.G. Hoffman and W.D. Wallis, Packing complete graphswith squares, Bulletin of the ICA 1 (1991), 89-92.
[5] J.A. Kennedy, Maximum packing of Kn with hexagons, Australas J combin 7 (1993), 101-110. Corrigendum: ibid 10 (1994), 293.
[6] C.C. Lindnetr and C.A. Rodger, “Decomposition into cycles II: Cycle systems,” Contemporary design theory: a collection of surveys, J.H. Dinitz and D.R. Stinson (Editors), Wiley, New York, 1992, pp. 325-369.
[7] C.C.Linder and C.A.Rodger, Design Theory. CRC Press L.L.C. 1997.
[8] A. Rosa and S. Znam, Packing pentagons into complete graphs: how clumsy can you get? Discrete Math 128 (1994), 305-316.
[9] J. Schonheim and A. Bialostocki, Packing and covering the complete graph with 4-cycles, Can Math Bull 18 (1975), 703-708.