k-退化圖的M圖的點(diǎn)蔭度.pdf

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

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

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

4、些已有的結(jié)論對(duì)k-退化作更深入的了解。
　　 第三章是本文最重要的一章，基于Andre Raspaud和Weifan Wang[8]證明的k-退化圖的點(diǎn)蔭度的結(jié)論va(G)≤[(κ+1)/2]，本文得到了以下三個(gè)結(jié)論：
　　 定理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-退化圖，