臺灣博碩士論文加值系統

圖形充填（含圖形分解）與許多數學結構有密切關係，而且其結果可廣泛地應用在其他領域，例如：編碼理論、多處理器網路、同步光纖網路、DNA篩選、實驗設計、排程問題等，已成為圖形理論中非常重要的一個研究主題。迴圈充填是特殊形式的圖形充填問題，現今這方面的研究仍極為盛行。
一個k-有向迴圈是長度為k的有向迴圈。多重邊有向圖G的一個邊互斥子圖集，若其中每個子圖皆同構於k-有向迴圈，則稱其為G的一個k-有向迴圈充填；若該充填的元素個數為最多，則稱其為最大充填。本論文探討完全二部重邊有向圖的最大4-有向迴圈充填，最大6-有向迴圈充填及最大8-有向迴圈充填問題。對於每個問題，本論文皆得到完整的解答。

Graph packing、including graph decomposition、is an important subject of graph theory since many mathematical structures are linked to it and its results can be applied in coding theory、multicomputer networks、synchronous optical networks (SONET)、DNA library screening、experimental design、scheduling、and other fields. Cycle packing is a special type of graph packing and continues to be a popular topic of research.
A k-circuit is a directed cycle of length k. For a multidigraph G、a k-circuit packing of G is a set of arc-disjoint k-circuits in G. A k-circuit packing of G which has the maximum number of members among all packings is referred as to a maximum k-circuit packing. In this thesis we investigate the problem of finding maximum packings of the complete bipartite multidigraphs with k-circuits for k=4、6 and 8、and give a complete solution to each case.

Contents
Abstract in Chinese……………………………………………………………………… i
Abstract in English……………………………………………………………………… ii
Acknowledge ……………………………………………………………………………. iii
Contents………………………………………………………………………………….. iv
List of Tables……………………………………………………….……………………. v
1. Introduction 1
1.1 Introduction to circuit packings….……………………………………………...1
1.2 Preliminaries………………………..……………………………………………3
1.3 Overview of the thesis………………………..………….………………………4
2. Packing Complete Bipartite Multidigraphs with 4-circuits 5
2.1 4-circuit decompositions………………………………………………………….. 5
2.2 Maximum 4-circuit packings……………………………...………….……...…… 6
3. Packing Complete Bipartite Multidigraphs with 6-circuits 9
3.1 6-circuit decompositions…………………………………………………..……….9
3.2 Maximum 6-circuit packings.……………………………………………..….…10
4. Packing Complete Bipartite Multidigraphs with 8-circuits 16
4.1 8-circuit decompositions………………….………………………………………16
4.2 Small cases………………………………………………………………..………18
4.3 Maximum 8-circuit packings…………………..………………………….………28
Bibliography 34




List of Tables
1.1 Definition of notations…………………….………………………..……………….3
2.1 The minimum leaves of 4-circuit packings of λK*m,n…………….........………….7
3.1 The minimum leaves of 6-circuit packings of λK*m,n……………........………….15
4.1 The minimum leaves of 8-circuit packings of λK*m,n……..…………..………….33

[1] F. E. Bennett and J. Yin 、Packings and coverings of the complete directed multi-
graph with 3- and 4-circuits、Discrete. Math. 162 (1996)、23-29.
[2] E. J. Billington、H.-L. Fu and C. A. Rodger、Packing complete multipartite graphs
with 4-cycles、J. Comb. Des. 9 (2001)、107-127.
[3] E. J. Billington、H.-L. Fu and C. A. Rodger、Packing ¸-fold complete multipartite
graphs with 4-cycles、Graphs Comb. 21 (2005)、169-185.
[4] L. Brown、G. Coker、R. Gardner and J. Kennedy、Packing the complete bipartite
graph with hexagons、Congr. Num. 174 (2005)、97-106.
[5] M. K. Fort、Jr. and G. A. Hedlund 、Minimal coverings of pairs by triples、Paci¯c
J. Math.、8 (1958)、709-719.
[6] H.-L. Fu and M.-H. Huang 、Packing balanced complete multipartite graphs with
hexagons、Ars Combin. 71 (2004)、49-64.
[7] D. G. Ho®man and W. D. Wallis 、Packing complete graphs with squares、Bull.
ICA 1 (1991)、89-92.
[8] J. A. Kennedy 、Maximum packings of Kn with hexagons、Australas. J. Combin.
7 (1993)、101{110 ; Corrigendum: ibid 10 (1994)、293.
[9] J.-J. Lin (in press)、Maximum packings of complete graphs with octagons、Ars
Combin.
[10] A. Rosa and S. Zn¶am 、Packing pentagons into complete graphs: how clumsy can
you get? Discrete Math. 128 (1994)、305-316.
[11] J. SchÄonheim and A. Bialostocki 、Packing and covering the complete graph with
4-cycles、Canad. Math. Bull. 18 (1975)、703-708.
[12] D. Sotteau、Decomposition of Km;n (K¤m;n) into Cycles (Circuits) of Length 2k、J.
Comb. Theory、Ser. B 30 (1981)、75-81.
[13] W.-C. Wu、H.-C. Lee and J.-J. Lin、Packing and covering complete bipartite
multidigraphs with 4-cycles、Ling Tung J. 24 (2008)、223-231.