t-裝填與t-覆蓋

Abstract

一個圖 的t-裝填是一族G的子圖H1,H2,...,Ht;任兩個圖同構而且沒有共同邊，同時每個圖的邊數恰為[|E(G)|/t]。一個圖G的t-覆蓋是一族彼此同構的t個圖H1,H2,...,Ht其中每個圖的邊數為[|E(G)|/t]+1而且G中所有邊包含在所有H的邊的聯集中。 在這一篇論文中，我們研究t-裝填(或t-覆蓋)中所產生的剩餘圖(增加圖)。對於所有t不大於6，我們把完全圖的所有可能在 -裝填(或 -覆蓋)所產生的剩餘圖(增加圖)全部找出來。

A t-packing of a graph G is a collection of t edge-disjoint isomorphic subgraphs of G such that each subgraph is of size [|E(G)|/t]. A t-covering of a graph G is a collection of t edge-disjoint isomorphic graphs H1,H2,...,Ht such that all edges of G contians in all union of edges of H's. In this thesis, we study the remainder graph (respectively, surplus graph) of each t-packing (respectively, t-covering) of the complete graph. For t is small than six, we determine all possible remainder graphs and respectively surplus graphs.