遞增子圖分割問題的研究

Abstract

把一個具有n （n ＋１）╱２個邊的圖分割成n 個遞增子圖的問題，最早是由Y.Ala- vi等五人所提出來的，實際上他們有下列的臆測。 臆測：一個有n （n ＋１）╱２邊的圖可被分割成n 個遞增子圖，而且子圖的邊數恰 為１，２，……，n 。 一個圖可被分割成像臆測中所說的一樣，則說它有遞增子圖分割（ASD ），如果它的 子圖是配對（matching）則為遞增配對子圖分割（AMD ），子圖是路徑（path）則為 遞增路徑子圖分割（APD ），如子圖是星星（star）則為遞增星星子圖分割（ATD ） 。 在本文中，最主要的目的是研究遞增子圖分割的問題。在第二章，我們研究遞增子圖 分割，先回顧一些已知結果，然後證明類似星星（star-like ）圖有遞增子圖分割。 接著，在第三章和第四章我們討論一些子圖為配對，路徑和星星的特殊分割。最後， 在第五章中我們證明臆測在輪子（wheel ）圖形中是正確的。