圖中參數(shù)與樹型結(jié)構(gòu)研究.pdf

1、幾十年來，圖的支撐樹特征問題一直是結(jié)構(gòu)圖論中一個(gè)重要的研究課題.該問題的產(chǎn)生和發(fā)展與結(jié)構(gòu)圖論中哈密爾頓問題的研究密切相關(guān)，因此受到國內(nèi)外許多圖論專家的關(guān)注。若圖中存在一條哈密爾頓路，即說明圖中存在恰好兩個(gè)葉子的支撐樹或是最大度等于2，即沒有分支點(diǎn)的支撐樹.自然就有如下問題:能否給出保證圖中存在至多k個(gè)葉子的支撐樹，或是圖中存在有限個(gè)分支點(diǎn)的支撐樹，或是圖中存在最大度不超過k的支撐樹等一系列問題的條件.同時(shí)，若圖為哈密爾頓連通圖，即說明圖

2、中存在以任意兩點(diǎn)作為葉子集的支撐樹，自然我們就可以試圖探求在何種條件下，圖中存在以任意k個(gè)點(diǎn)作為葉子集的支撐樹，由此引出k-葉子連通圖的判定問題.
　　眾所周知，判定一個(gè)圖是否含一條哈密爾頓路從算法復(fù)雜性來講是NP-完全的，從而對(duì)上述一系列有關(guān)保證圖中是否存在具有相應(yīng)特征的支撐樹問題也是NP-完全的，于是對(duì)于這些問題的研究主要集中在給出相應(yīng)的充分條件.
　　目前在圖中是否存在具有和哈密爾頓性相關(guān)的特征的支撐樹問題的研究中主要

3、從參數(shù)的角度進(jìn)行刻畫，運(yùn)用堅(jiān)韌度、獨(dú)立數(shù)、連通度、領(lǐng)域并、度和等條件，集中討論圖中是否存在以下五類特征的支撐樹的充分條件:1.圖中存在最大度不超過k的支撐樹;2.圖中存在至多k個(gè)分支點(diǎn)的支撐樹;3.給定連通度條件下，圖中，特別地，K1,r-free圖中存在至多k個(gè)葉子的支撐樹;4.圖中存在以任意k個(gè)點(diǎn)作為葉子集的支撐樹;5.圖中存在滿足去掉所有葉子后，最大度至多為k的支撐樹.
　　本文主要研究了在滿足一定連通度條件下，K1，4-f

4、ree圖和K1，5-free圖中存在至多有限個(gè)葉子的支撐樹的度和條件.首先考慮連通K1，4-free圖，Kyaw證明了若圖G是階數(shù)為n的連通K1,4-free圖，(i)若σ3(G)≥n，則G中含一條哈密爾頓路，即恰含兩個(gè)葉子的支撐樹;(ii)當(dāng)k≥3時(shí)，若σk+1(G)≥n-k/2，則G中存在至多k個(gè)葉子的支撐樹.并且說明了結(jié)論中的界均為最好可能的.本文提高連通度，考慮m-連通K1,4-free圖.證明了圖G是階數(shù)為n的m-連通K1，4