圖的上可嵌入性與3-正則圖的最大虧格.pdf

1、本篇論文主要研究了拓撲圖論中的一個十分活躍的方面——圖的上可嵌入性和最大虧格，它是圖的曲面可嵌入性理論的一個重要研究課題。圖的曲面可嵌入性起源于著名的四色問題。自從Cayley1878年正式公布了四色問題后，圖的平面可嵌入性問題便開始引起了人們的關(guān)注。1890年Heawood對一般的曲面提出了類似的地圖著色問題后，圖的曲面可嵌入性問題便進一步提出來了，特別是Hilbert和Cohn-Vossen將四色問題化為確定Kn的引線問題(Kn的引

2、線問題等價于求其虧格)。雖然，地圖著色問題于1968年得到解決，它的解法卻導(dǎo)致了一個新的數(shù)學(xué)分支——拓撲圖論的產(chǎn)生，圖的曲面可嵌入性就成了這一數(shù)學(xué)分支的一個主要研究內(nèi)容。這里的圖是指連通圖，曲面是指一個連通緊致的2維閉流形(可定向或不可定向均可)。圖的一個嵌入是指存在一個從圖到曲面的拓撲映射使從曲面上去掉圖的頂點和邊后的每個連通分支都拓撲同胚于一個開圓盤，這樣的嵌入也稱為2-胞腔嵌入。圖的(最小)虧格γ(G)是指最小的整數(shù)g使之在曲面S

3、g有2-胞腔嵌入，而圖的最大虧格γM(G)是指最大的整數(shù)g使之在曲面Sg有2-胞腔嵌入。圖的虧格具有介值性質(zhì)，即對于最小虧格和最大虧格之間的任一整數(shù)g存在圖G在Sg上的2-胞腔嵌入。達到最大虧格上界的嵌入稱為上可嵌入。由于已經(jīng)證明了任一連通圖在不可定向曲面上的最大虧格等于其圈秩，因此這里關(guān)于曲面上可嵌入性的討論均指是在可定向曲面上。 拓撲圖論不僅豐富了拓撲學(xué)的內(nèi)容，也使圖論的面目一新，使人們對圖和曲面有了更為深刻的認識?？紤]到圖

4、在曲面上的上可嵌入性及圖的一些性質(zhì)如邊連通度、獨立集和獨立數(shù)、3-正則等以及N.Xuong1979年、L.Nebesky1981年分別給出的圖的上可嵌入性的兩個充要條件，本文主要利用了黃元秋1999年給出的非上可嵌入圖的結(jié)構(gòu)特征，給出了一些新的上可嵌入圖類，使圖論中的一些上可嵌入性問題得到了解決。本篇論文作了以下主要工作： 1、結(jié)合邊連通度，探討了獨立集中具有最小特定度和的上可嵌入圖類。 2、刻畫了邊連通簡單圖中具有特定