完全重邊圖之短路徑充填與覆蓋

Packing and Covering the Complete Multigraphs with Short Paths

陳薇琳(Wei-Lin Chen)

指導教授 ： 李鴻志

嶺東科技大學/資訊學院/資訊科技應用研究所/碩士(2012年)

https://doi.org/10.6823/LTU.2012.00034

摘要

圖形充填與覆蓋（含圖形分解）與許多數學結構有密切關係，且其結果可廣泛地
應用在其他領域，例如：編碼理論、同步光纖網路、多處理器網路、實驗設計、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.

並列關鍵字

complete graph ； path ； packing ； covering ； leave ； padding

參考文獻

[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.