關(guān)于一些特殊圖的上可嵌入性研究.pdf

1、自從E.Nordhaus，B.Stewart和A.White等人引進(jìn)圖的最大虧格概念以來，圖的上可嵌入性嵌入引起人們的廣泛關(guān)注.由R.Duck圖的虧格插值定理知：考慮圖G的所有可定向嵌入的曲面，只需確定它的虧格r(G)與最大虧格rM(G).圖G的最大虧格rM(G)是指存在最大的整數(shù)k使得G在虧格為k的可定向曲面S上有2-胞腔嵌入.由于圖在任意曲面上的2-胞腔嵌入至少有一個面，由Euler公式知：rM(G)≤[β(G)/2]，這里β(G)

2、E(G)｜-｜V(G)｜+1稱為圖G的Betti數(shù).如果rM(G)=[β(G)/2]，稱圖G是上可嵌入的. 關(guān)于圖的上可嵌入性，劉彥佩[5]和Nebskey[7]分別給出了不同形式的充要條件;黃元秋和劉彥佩[18]從另一相反角度出發(fā)，提供了一個關(guān)于不是上可嵌入圖的充要條件.由此充要條件，本文主要對一些滿足特殊條件的圖的上可嵌入性進(jìn)行專門研究，共分為五章. 在第一章中：集中探討范條件圖的上可嵌入性.設(shè)G是2點(diǎn)連通圖，若對任

3、一對使d(u，v)=2的點(diǎn)u，v，滿足max{d(u)，d(v)｝≥n/2(其中n=｜V(G)｜)，則稱G是滿足范條件的圖；我們證明了范條件圖是上可嵌入的.在第二章中：集中探討大次和條件圖的上可嵌入性.設(shè)G是k點(diǎn)連通圖，若對任一{x1，x2，…，xk+1}-獨(dú)立集均有d(x1)+d(x2)+…+d(xk+1)≥n-k(n=｜V(G)｜)，則稱G是滿足大次和條件的圖;我們證明了2類大次和條件圖是上可嵌入的.在第三章中：集中探討G的立方圖G

4、3的上可嵌入性.設(shè)G=(V，E)，定義Gk=(V(Gk)，E(Gk))，其中V(Gk)=V(G)，E(Gk)={e=uv｜dG(u，v)≤k｝，則稱Gk為G的k方圖；我們證明了G的立方圖G3是上可嵌入的. 在第四章中：集中探討特殊二部圖的上可嵌入性.我們證明下述結(jié)果：(1)設(shè)G=(X，Y；E)，定義G3=(V(G3)，E(G3))，其中V(G3)=V(G)，E(G3)=E(G)U{e=xy｜dG(x，y)=3，x∈X，y∈Y}，

5、則G3是上可嵌入的；(2)設(shè)G=(X，Y；E)，｜X｜=｜Y｜=n(n≥3)，對任一對dG(x，y)=3的x∈X，y∈Y，均有d(x)+d(y)≥n+1，則G是上可嵌入的. 在第五章中：簡單地探討3-正則圖的上可嵌入性.我們討論3-正則圖的葉子數(shù)與最大虧格rM(G)之間的關(guān)系并給出3-正則圖最大虧格的一個計算公式：rM(G)=1/2[l(T)+pα-pβ]，這里T是Xuong樹，l(T)是T的葉子數(shù)，pα，pβ分別是G-E(T)