分割完全圖成有預定長度的路徑

Abstract

把具有奇數點的完全圖分割成有預定長度的一些圈是一個相當知名的問題,到目前為止,只有部分特殊的結果. 在這篇論文中,我們將探討一個看起來比較有希望完全解決的類似問題:把完全圖分割成一些具有預定長度的路徑. 我們主要的結果是證明在最小路徑不太大的情況下完全圖可以適當地加以分割.

Decomposing $K_{2n+1}$ or $K_{2n}-I$ into cycles with prescribed lengths has been an interesting problem in graph decomposition since 1980 (posed by B. Alspach). So far, only some special cases are solved. In this thesis we shall study an analog of the problem which looks like more solvable. Instead of cycle decomposition, we shall decompose the complete graph $K_n$ into paths with prescribed lengths. Mainly, we proved that if the smallest prescribed length is not too small or the one rest to the smallest one is not too large, then $K_n$ can be decomposed properly.}