完全圖的極大路徑填充

Abstract

圖G的H-填充是一個蒐集一些G中邊兩兩互相不同的子圖的集合℘={H_1,H_2,…,H_s }，其中每一個子圖H_i都和H同構。我們將那些沒有被H_i用到的邊集合所導出的子圖稱為此填充的殘留。若殘留的部分找不到一個子圖和H同構的話，則稱此填充為極大填充。每一個極大填充不一定擁有同樣多的基數。令S(G;H)為一蒐集圖G所有極大H-填充的基數的集合。如果圖G是一個有n個點的完全圖，則將S(K_n;H)簡化為S(n;H)。 在此篇論文中，我們將探討S(n;P_(k+1) )，其中P_(k+1)是一條有k+1個點的路徑。值得注意的是，一個K_n的極大P_(k+1)-填充若其基數為S(n;P_(k+1) )中的最小值，則此填充為K_n的最小P_(k+1)-填充且其殘留恰會是一個限制子圖為P_(k+1)的極圖。反之，一個K_n的極大P_(k+1)-填充若其基數為S(n;P_(k+1) )中的最大值，則此填充為K_n的最大P_(k+1)-填充。

An H-packing P = fH1;H2; : : : ;Hsg of a graph G is a set of edge-disjoint subgraphs of G in which each subgraph Hi is isomorphic to H. The leave L of P is the subgraph induced by the set of edges of G that does not occur in any Hi. P is a maximal H-packing if L contains no subgraph that is isomorphic to H. Let S(G;H) denote the set of all possible cardinality of P such that P is a maximal H-packing of G. In case that G is the complete graph of order n, we use S(n;H) to denote S(Kn;H) for convenience. In this thesis, we focus on the study of S(n; Pk+1) where Pk+1 is a path with k + 1 vertices. Notice that the leave of the packing which attends min S(n; Pk+1) is the extremal graph which forbids Pk+1 and the packing which attends max S(n; Pk+1) is a maximum packing of Kn with Pk+1's.The main result obtained in this thesis is that we determine S(n; Pk+1) for k = 3; 4; 5; 6.