臺灣博碩士論文加值系統

圖形充填與覆蓋（含圖形分解）與許多數學結構有密切關係，且其結果可廣泛地
應用在其他領域，例如：編碼理論、同步光纖網路、多處理器網路、實驗設計、DNA
篩選、排程問題等，已成為圖形理論中非常盛行的一個研究主題。
k-路徑是長度為k 之路徑。本論文分別探討全完重邊圖之3-路徑、4-路徑及5-
路徑充填與覆蓋問題，且得到所有最大充填與最小覆蓋。

Graph packing and covering, graph decomposition included, has been and continues
to be a popular topic of research in graph theory since many mathematical structures are
linked to it and its results can be applied in coding theory, synchronous optical networks
(SONET), multicomputer networks, experimental design, DNA library screening,
scheduling and other fields.
A k-path is a path of length k. In this thesis we completely solve the problem of
finding maximum packings and minimum coverings of complete multigraphs with k-paths
for k =3,4,5.

Contents
Abstract in Chinese……………………………………………………………………… i
Abstract in English……………………………………………………………………… ii
Acknowledgement……………………………………………………………………… iii
Contents………………………………………………………………………………… iv
List of Tables………………………………………………………………………………… v
1. Introduction to packings and coverings 1
1.1 Introduction……………………………………………………………………… 1
1.2 Preliminaries…………………………………………………………………… 3
1.3 Overview of the thesis………………………………………………………… 4
2. Packing and Covering Complete Multigraphs with 3-paths 7
2.1 Minimum possible leaves and paddings……………………………………… 7
2.2 Maximum 3 P -packings and minimum 3 P -coverings…………………………… 8
3. Packing and Covering Complete Multigraphs with 4-paths 11
3.1 Minimum possible leaves and paddings……………………………………… 11
3.2 Maximum 4 P -packings and minimum 4 P -coverings………………………… 12
4. Packing and Covering Complete Multigraphs with 5-paths 22
4.1 Minimum possible leaves and paddings……………………………………… 22
4.2 Maximum 5 P -packings and minimum 5 P -coverings………………………… 23
Bibliography 39

[1] P. Adams, D. E. Bryant and S. I. El-Zanati, Packing and covering the complete
graph with cubes, Australas. J. Combin. 20 (1999), 267-288.
[2] E. J. Billington and C. C. Lindner, Maximum packings of bowtie designs, J.
Combin. Math. Combin. Comput. 27 (1998), 227-249.
[3] A. E. Brouwer, Optimal packings of Kn into K4's, J. Combin. Theory Ser. A 26
(1979), 278-297.
[4] D. Bryant and D. Horsley, Packing cycles in complete graphs, J. Combin. Theory Ser. B 98 (2008), 1014-1037.
[5] S. I. El-Zanati, Maximum packings with odd cycles, Discrete Math. 131 (1994),
91-97.
[6] M. K. Fort, Jr. and G. A. Hedlund, Minimal coverings of pairs by triples, Pacific J. Math. 8 (1958), 709-719.
[7] C. M. Grinstead, On coverings and packings of the complete graph with cycles,
Ars Combin. 3 (1977), 25-37.
[8] D. G. Hoffman, C. C. Lindner, M. J. Sharry and A. P. Street, Maximum packings
of Kn with copies of K4-e, Aequationes Math. 51 (1996), 247-269.
[9] D. G. Hoffman and W. D. Wallis, Packing complete graphs with squares, Bull.
ICA 1 (1991), 89-92.
[10] M. Li, J. Huo and Z. Gao, Maximum packings and minimal coverings of kv with
octagons, Graphs Combin. 25 (2009), 735-752.
[11] J.-J. Lin, Maximum packings of complete graphs with octagons, Ars Combin. 97
(2010), 479-495.
[12] C. C. Lindner and A. P. Street, Simple minimum coverings of Kn with copies of K4-e, Aequationes Math. 52 (1996), 284-301.
[13] C. C. Lindner and A. P. Street, Multiple minimum coverings of Kn with copies of K4-e, Utilitas Math. 52 (1997), 223-239.
[14] S. Milici, Coverings of a complete graph with five-vertex and five-edge graphs, Discrete Math. 284 (2004), 225-229.
[15] W. M. Mills, On the covering of pairs by quadruples-I, J. Combin. Theory 13
(1972), 55-78.
[16] W. M. Mills, On the covering of pairs by quadruples-II, J. Combin. Theory 15
(1973), 138-166.
[17] C. A. Parker, Complete bipartite graph path decompositions, Thesis, Auburn University, Auburn, Alabama (1998).
[18] Y. Roditty, Packing and covering of the complete graph with a graph G of four vertices or less, J. Combin. Theory Ser. A 34 (1983), 231-243.
[19] Y. Roditty, Packing and covering of the complete graph. IV. The trees of order seven, ARS Combin. 35 (1993), 33-64.
[20] A. Rosa and S. Znam, Packing pentagons into complete graphs: How clumsy can
you get? Discrete Math. 128 (1994), 305-316.
[21] J. SchÄonheim, On maximal systems of k-tuples, Studia. Sci. Math. Hung. 1 (1966), 363-368.
[22] J. SchÄonheim and A. Bialostocki, Packing and covering the complete graph with 4-cycles, Canad. Math. Bull. 18 (1975), 703-708.
[23] R. G. Stanton and M. J. Rogers, Packings and coverings by triples, ARS Combin. 13 (1982), 61-69.
[24] M. Tarsi, Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs, J. Combin. Theory Ser. A 34 (1983), 60-70.