圖的圈填充之研究

Abstract

一個圖G的k圈填充是圖G邊中不互相相同的k圈集合。然而並不是所有的圖都可以被k圈填充，我們將剩下的邊集合所導出的子圖稱為這個裝填的殘留。能夠將殘留的部分邊數最少的裝填又稱為是最大的裝填。此時殘留的部分自然是最小殘留。 對應於裝填的觀念，我們也可考慮用k圈來覆蓋圖G。不夠的部分需加一些補丁， 如果補丁所用的邊數為最少，則此為最小覆蓋。 研究填充與覆蓋的問題已有百多年的歷史了，而最有名的題目就是完全圖的3圈填充。在此論文中我們著眼於5圈及 6圈的填充而考慮的圖形為平衡的完全多部分圖及兩個完全圖的卡笛森運算。

A $k$-$cycle$ $packing$ of a graph $G$ is a set of edge-disjoint $k$-cycles in $G$. A $k$-cycle packing $C$ is $maximum$ if $|C|\geq |C'|$ for all other $k$-cycle packings $C'$ of $G$. The $leave$ $L$ of a packing $C$ is the subgraph induced by the set of edges of $G$ that does not occur in any $k$-cycle of the packing $C$. Therefore a maximum packing has a minimum leave. A $k$-$cycle$ $covering$ of $G$ is a set of edge-disjoint $k$-cycles $\mathcal{C}$ such that each edge of $E(G)$ occurs in at least one $k$-cycle in $\mathcal{C}$. A $k$-cycle covering $\mathcal{C}$ is $minimum$ if $|\mathcal{C}|\leq |\mathcal{C'}|$ for all other $k$-cycle coverings of $G$. The graph induced by the set of edges which are added to $G$ in the covering is called the $padding$ of the covering. Clearly, a minimum padding can be obtained in a minimum covering. The study of packing and covering problem commenced more than one hundred years ago. The most famous one is a $3$-cycle packing (respectively, covering) of the complete graph $K_{v}$. In case that the leave of a 3-cycle packing is an empty graph, we have a Steiner triple system of order $v$. It is indeed very closely related to the study of combinatorial designs. In this thesis, we shall focus on the study of 5-cycle and 6-cycle packings (respectively, coverings). By considering $G$ as the balanced complete multipartite graphs $K_{m(n)}$ and the Cartesian product of two complete graphs $K_{m}\times K_{n}$, we have obtained several results which will be presented in chatpers two to six.