k-退化圖的M圖的點蔭度.pdf

1、本文中所涉及的圖均為有限簡單圖。圖G的點蔭度va(G)是由Chartrand，Kronk和Wall[1]最早提出來的，而且他們在文[1]中證明了平面圖的點蔭度va(G)≤3。在本文中，我們所要證明了k-退化圖的M圖的點蔭度va(G)≤[(κ+1)/2]，其中，2-退化圖、3-退化圖的點蔭度va(G)=2。
　　 圖G的點蔭度為圖G的頂點集V(G)的最小劃分數(shù)，其中每個點劃分集的導出子圖是一個森林，記為va(G)[8]。
　

2、　 若圖G的任一子圖H均含有一個度至多為κ的頂點，則稱圖G為k-退化圖[8]。
　　 由簡單圖G產生包含G的一個簡單圖G'，從頂點集合為{v1… vn}的圖G開始，添加頂點集U={u1…un}和一個另外的頂點ω，然后添加一些邊使得ui與NG(vi)中的頂點都鄰接，最后令N(ω)=U，稱G'為G的Mycielski圖[26]，簡稱M圖。
　　 在文[24]中，Garey和Johnson證明了導出森林的k-劃1分(κ≥3)

3、問題是NP-完全問題，故圖G的點蔭度也為NP-完全問題。對于點蔭度問題，非平面圖的點蔭度的計算非常困難，所以目前主要研究的是平面圖的點蔭度。本文中，主要研究k-退化圖的M圖的點蔭度，而大部分的k-退化圖的M圖為非平面圖。
　　 首先，我們在第一章中較為詳細地介紹了圖論的一些背景知識及相關概念。同時，我們對本文所要研究的k-退化圖以及圖的點蔭度作了詳細的介紹。
　　 在第二章中，主要是介紹一些k-退化圖已有的結論，借助于這

4、些已有的結論對k-退化作更深入的了解。
　　 第三章是本文最重要的一章，基于Andre Raspaud和Weifan Wang[8]證明的k-退化圖的點蔭度的結論va(G)≤[(κ+1)/2]，本文得到了以下三個結論：
　　 定理3.2.2若圖G為2-退化圖，H為G的M圖，則va(H)=2；
　　 定理3.2.3若圖G為3-退化圖，H為G的M圖，則va(H)=2；
　　 定理3.2.4若圖G為k-退化圖，