遞增子圖分割

Abstract

把一個圖分割成遞增子圖的問題首先是由Y.Alavi 等五人所提出的，最近這個問題已 有了些進展，到目前為止是下列的圖已經被證明都可以如此分割；它們是星星森林（ star forest ），分支度（degree）是質數次冪的正則圖（regular graph ），完全 兩部分圖（complete bipartite graph），和最大分支度（maximum degree）不大於 （n ＝１）╱２的圖具有遞增子圖分割，本文首先在第二章列出一些已知的結果，然 後在第三、四章中，我們介紹另外兩種新的圖形分割法，最後我們證明以下的圖具有 遞增子圖分割，它們是：像星星圖的森林（star-like forest），毛蟲（族）（cat- erpillar（family））和長腿毛蟲（族）（long-leg caterpillar（family））。