圖的上可嵌入性.pdf

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

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

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