圖的上可嵌入性.pdf

1、圖的最大虧格是刻劃圖在某個(gè)定向曲面上是否有2-胞腔嵌入的一個(gè)特征參數(shù).對(duì)這一參數(shù)的研究是拓?fù)鋱D論的主要問題之一.而確定一類圖的上可嵌入性問題本身就是確定圖的最大虧格問題.結(jié)合圖的一個(gè)或多個(gè)參數(shù),許多文獻(xiàn)都給出了若干上可嵌入圖類<'[7-14]>,即給出了最大虧格達(dá)到最好上界|β(G)/2|的圖類;或給出一些圖類的最大虧格的較好下界<'[15-31]>.該文的第一個(gè)主要結(jié)果,根據(jù)圖的頂點(diǎn)劃分和點(diǎn)的度的條件,研究圖的上可嵌入性.圖G的C-劃

2、分是指:G的一個(gè)頂點(diǎn)劃分{V<,1>,V<,2>,……,V<,k>}使得每個(gè)G{V<,i>]為多重完全圖(1≤i≤k),證明了如下結(jié)果:設(shè)G為連通圖,且對(duì)任意v∈V(G),d<,G>(v)≡1(mod4).若G的頂點(diǎn)集存在一個(gè)C-劃分{V<,1>,V<,2>,………,V<,k>},使得對(duì)每一個(gè)1≤i ≤k,|V<,i>≥4且|V<,i>|≡0(mod4),則G是上可嵌入的.該文的第二個(gè)主要結(jié)果,利用圖在曲面上的嵌入特征,特別是面的度的大

3、小,研究圖的最大虧格下界或上可嵌入性.黃元秋教授和劉彥佩教授在文獻(xiàn)[18]中證明了R.Nedeal和M.Skoviera在文獻(xiàn)[17]中所提的一個(gè)猜想:若一個(gè)(簡(jiǎn)單)圖G存在某個(gè)(定向或不定向曲面嵌入使得G的每個(gè)面的度不超過7,則G是上可嵌入的,即ξ(G)≤ 1.同時(shí),文獻(xiàn)[18]說明條件"面的度不超過7"是必要的.自然地,若一個(gè)圖G在某個(gè)曲面嵌入中存在度超過7的面,一個(gè)值得回答的問題是:ξ(G)的上界情況怎樣,或者等價(jià)地,G的最大虧格