樹圖和大次和條件圖的上可嵌入性研究.pdf

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

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

3、圖的樹圖的上可嵌入性.雙圈圖An(1，l2)的樹圖是l1+l2-2正則圖，且是上可嵌入的，其最大虧格為：γM(GT)=[β(GT)/2]=[l1·l2·(l1+l2-4)+2/4]-γM(GT)=β(GT)=l1·l2·(l1+l2-4)/2+1.在第二章中：集中探討了連通圖的(鄰接)樹圖的上可嵌入性.若圖G可2胞腔嵌入到可定向曲面S上，且G嵌入S后至多只有2個(gè)面，稱G在S上是上可嵌入的。本文證明了如下結(jié)果：若圖G是連通圖，則G的鄰接樹

4、圖G1、樹圖GT都是上可嵌入的. 在第三章中：集中探討大次和條件圖的上可嵌入性.設(shè)G是k點(diǎn)連通圖，若對(duì)任一{X1，X2，…，Xk+1}-獨(dú)立集均有d(x1)+d(x2)+…+d(xk+1)≥n-k(n=|V(G)|)，則稱G是滿足大次和條件的圖；我們證明了如下結(jié)果：若大次和條件圖G是簡(jiǎn)單圖，則G是上可嵌入的.本章還指出了，若大次和條件圖G不是簡(jiǎn)單圖，不一定是上可嵌入的，并分別給出幾個(gè)不能上可嵌入的大次和條件圖. 在第四章