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

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

2、線問題等價(jià)于求其虧格)。雖然，地圖著色問題于1968年得到解決，它的解法卻導(dǎo)致了一個(gè)新的數(shù)學(xué)分支——拓?fù)鋱D論的產(chǎn)生，圖的曲面可嵌入性就成了這一數(shù)學(xué)分支的一個(gè)主要研究內(nèi)容。這里的圖是指連通圖，曲面是指一個(gè)連通緊致的2維閉流形(可定向或不可定向均可)。圖的一個(gè)嵌入是指存在一個(gè)從圖到曲面的拓?fù)溆成涫箯那嫔先サ魣D的頂點(diǎn)和邊后的每個(gè)連通分支都拓?fù)渫哂谝粋€(gè)開圓盤，這樣的嵌入也稱為2-胞腔嵌入。圖的(最小)虧格γ(G)是指最小的整數(shù)g使之在曲面S

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

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