關(guān)于最大虧格與其它不變量.pdf

1、圖在曲面上的嵌入起源于地圖著色定理的證明.這里,曲面S就是無邊緣的緊2-維閉流形,分為可定向曲面與不可定向曲面.連通圖G在曲面S上的2-胞腔嵌入,簡稱為嵌入,是指存在一個1—1連續(xù)映射φ:G→S使得S-φ(G)的每個連通分支都同胚于一個開圓盤.圖G的最小虧格,γ(G),就是最小的整數(shù)n使得圖G能嵌入到虧格為n的可定向曲面Sn.圖G的最大虧格,γM(G),就是最大的整數(shù)n使得圖G能嵌入到虧格為n的可定向曲面Sn.1966年,Duke[12

2、]得到了可定向曲面嵌入的插值定理:若圖G可嵌入到可定向曲面Sn和Sm(n≤m),則對任意的整數(shù)g,n≤g≤m,圖G可嵌入到可定向曲面Sg.因此,圖G的最大和最小虧格確定了圖G能嵌入的全部可定向曲面.相似的,可定義最大不可定向虧格和最小不可定向虧格.關(guān)于圖G的最大不可定向虧格(γ)M(G),劉彥佩教授[36],Ringel以及Stahl分別獨立地證明了
　　 (γ)M(G)=ε(G)-v(G)+1.
　　 于是,我們只需考

3、慮圖在可定向曲面上的最大虧格.
　　 因為圖G在任意曲面上的嵌入至少有一個面,由Euler公式易得γM(G)≤[β(G)/2].
　　 其中,β(G)=ε(G)-v(G)+1稱為圖G的Betti數(shù)；[x]表示不超過x的最大整數(shù).若γM(G)=[β(G)/2],則稱圖G是上可嵌入的.
　　 本論文主要結(jié)合圖的一些不變量,如最小度,圍長,頂點數(shù),獨立數(shù),頂點的度和等,研究了圖的上可嵌入性以及圖的最大虧格的下界,并給出

4、了非上可嵌入的3-正則圖的結(jié)構(gòu)特征.具體分為以下七章.
　　 第一章,首先對圖在曲面上嵌入的研究背景及發(fā)展作了簡單介紹.其次,給出了圖論的一些基本概念和術(shù)語以及圖的最大虧格的一些基本性質(zhì).
　　 第二章,結(jié)合圖的最小度和圍長,從研究圖的給定子圖的頂點數(shù)出發(fā),我們得到了圖的上可嵌入性與頂點數(shù)之間的關(guān)系.
　　 第三章,結(jié)合圖的最小度和圍長,給出了非上可嵌入連通圖的最大虧格的新下界.
　　 第四章,結(jié)合圖的圍

5、長,從研究圖的給定子圖內(nèi)相鄰頂點的度和出發(fā),得到了圖的上可嵌入性與相鄰頂點度和的關(guān)系.
　　 第五章,結(jié)合圖的最小度和圍長,從研究圖的給定子圖內(nèi)獨立數(shù),非相鄰頂點的度和出發(fā),得到了圖的上可嵌入性與獨立數(shù),非相鄰頂點的度和之間的關(guān)系.
　　 第六章,研究了非上可嵌入的2-邊連通3-正則圖的結(jié)構(gòu),補充了文獻[28]中關(guān)于上可嵌入的2-邊連通3-正則圖的結(jié)構(gòu).
　　 第七章,提出了一些進一步研究的問題,如計算圖的最大虧