關(guān)于圖的最大虧格研究.pdf

1、自E.A.Norldaus，B.M.Stewart和A.T.White[1]等人于上世紀(jì)70年代初提出圖的最大虧格概念以來，先后有許多圖論學(xué)者都投身于這一拓?fù)鋮?shù)的研究．由于N.H.Xuong[2]，Y.P.Liu[3]等于上個世紀(jì)70年代末分別獨(dú)立地給出了刻畫圖的最大虧格的表示定理和L.Nebesky[4]于上個世紀(jì)80年代初又給出了圖的最大虧格的另一種對偶形式的刻畫，因此關(guān)于圖的最大虧格的研究取得了很重要的進(jìn)步．上世紀(jì)90年代末，黃

2、元秋的博士論文[5]對圖的最大虧格進(jìn)行了系統(tǒng)地研究及簡化.目前，對于圖的最大虧格研究主要集中在2個方面，一方面：希望能確定一些上可嵌入圖類，即其最大虧格可取得最好的上界[β(G)/2]；另一方面：希望得到一些非上可嵌入圖類的由圖的其它參數(shù)表示的最大虧格下界.本文主要從以上兩方面進(jìn)一步研究圖的最大虧格，得到了一些新的上可嵌入圖類，及一些圖類的最大虧格較好的下界，推廣了相關(guān)結(jié)果.本文的主要結(jié)果如下： (1)若G為2-邊連通簡單圖，且

3、滿足以下條件之一： (a)α(G)≤2； (b)α(G)≥3，且對于任何彼此不相鄰的三個頂點(diǎn)vi(i=1，2，3)都有 3∑i=1dG(vi) ≥|V(G)|-3g(G)+7,則G是上可嵌入的，其中下界“V|(G)|-3g(G)+7”是最好的．對于3-邊連通圖也有類似的結(jié)果．這推廣了。Y.C.Chen[6]的結(jié)果. (2)設(shè)G為k-邊連通圖，滿足： a'(G)≤((k-1)2+2[g(G)/2]+1+(-1)(g

4、(G)+1)/2((k-1)(k-2)+1)-1其中k=1，2，3，則G是上可嵌入的．且不等式的上界是最好的．這推廣了Y.C.Chen[7]的結(jié)果． (3)設(shè)G為k-邊連通簡單圖，若對G中任意圈C，存在點(diǎn)x∈C滿足： dG(x)>|V(G)|/[(k-1)2+2]+k-g(G)+2,k=1,2,3,則G是上可嵌入的．且不等式的下界是最好的．關(guān)于這方面的結(jié)果，目前尚屬首次． (4)設(shè)G是簡單連通圖，則ξ(G)≤α(