標題: 遞增子圖分割
作者: 胡維新
HU, WEI-XIN
傅□霖
FU, HENG-LIN
應用數學系所
關鍵字: 遞增子圖;分割;星星森林;分支度;正則圖;毛蟲族;STAR-FOREST;DEGREE;REGULAR-GRAPH;CATERPILLAR-FAMILY;ALAVI-Y.
公開日期: 1987
摘要: 把一個圖分割成遞增子圖的問題首先是由Y.Alavi 等五人所提出的,最近這個問題已 有了些進展,到目前為止是下列的圖已經被證明都可以如此分割;它們是星星森林( star forest ),分支度(degree)是質數次冪的正則圖(regular graph ),完全 兩部分圖(complete bipartite graph),和最大分支度(maximum degree)不大於 (n =1)╱2的圖具有遞增子圖分割,本文首先在第二章列出一些已知的結果,然 後在第三、四章中,我們介紹另外兩種新的圖形分割法,最後我們證明以下的圖具有 遞增子圖分割,它們是:像星星圖的森林(star-like forest),毛蟲(族)(cat- erpillar(family))和長腿毛蟲(族)(long-leg caterpillar(family))。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT762507009
http://hdl.handle.net/11536/53538
顯示於類別:畢業論文