均勻完全二部圖之多重充填與覆蓋

圖形充填與覆蓋（含圖形分解）為圖形理論中非常盛行的一個研究主題，而其結果可廣泛地應用在其他領域，例如：編碼理論、同步光纖網路等問題的處理上。本論文得到均勻完全二部圖的(G,H)-多重分解，其中，G與H為k-路徑，k-星形或k-迴圈。在此問題上，我們得到一些充要條件。此外，本論文亦探討均勻完全二部圖的小圖多重充填與多重覆蓋，並完全解決最大多重充填與最小多重覆蓋問題。

關鍵字

均勻完全二部圖；路徑；星形；迴圈；多重分解；多重填充；多重覆蓋

並列摘要

Graph packing and covering, graph decomposition included, has been and continues to be a popular topic of research in graph theory, and its results can be applied in coding theory, synchronous optical networks (SONET) and other fields. In this thesis, we obtain necessary and sufficient conditions for the existence of a (G,H)-multidecomposition problem of the balanced complete bipartite graph where G and H are a k-path, a k-star or a k-cycle. Moreover, we consider the multipackings and multicoverings of balanced complete bipartite graph with pairs of small G and H, and give the complete solutions to the maximum multipacking and minimum multicovering problems.