圖的上可嵌入性.pdf

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

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

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