树图和大次和条件图的上可嵌入性研究

摘要

自从E.Nordhaus，B.Stewart和A.White等人引进图的最大亏格的概念以来，最大亏格及其相关概念图的上可嵌入性嵌入引起人们的广泛关注.由R.Duck图的亏格插值定理知：考虑图G的所有可定向嵌入的曲面，只需确定它的亏格r(G)与最大亏格rM(G).G的最大亏格rM(G)是指存在最大的整数k使得G在亏格为k的可定向曲面S上有2-胞腔嵌入.由于图在任意曲面上2-胞腔嵌入至少有一个面，由Euler公式知：rM(G)≤[β(G)/2]，这里β(G)=|E(G)|-|V(G)|+1称为图G的Betti数.如果rM(G)=[β(G)/2]，称图G是上可嵌入的. 关于图的上可嵌入性，刘彦佩[5]和Nebskey[7]分别给出了不同形式的充要条件；黄元秋和刘彦佩[19]从另一相反角度出发，提供了一个关于不是上可嵌入图的充要条件.由此充要条件，本文主要对一些满足特殊条件的图的上可嵌入性和树图的上可嵌入性进行专门研究，共分为四章. 在第一章中：集中探讨了双圈图的树图的上可嵌入性.双圈图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在S上是上可嵌入的。本文证明了如下结果：若图G是连通图，则G的邻接树图G1、树图GT都是上可嵌入的. 在第三章中：集中探讨大次和条件图的上可嵌入性.设G是k点连通图，若对任一{X1，X2，…，Xk+1}-独立集均有d(x1)+d(x2)+…+d(xk+1)≥n-k(n=|V(G)|)，则称G是满足大次和条件的图；我们证明了如下结果：若大次和条件图G是简单图，则G是上可嵌入的.本章还指出了，若大次和条件图G不是简单图，不一定是上可嵌入的，并分别给出几个不能上可嵌入的大次和条件图. 在第四章中：本章给出一个三角等式的初等证明，同时给出了这三角等式的两种高数证法及一个图论证明，体现了高等数学在解决一些初等问题上的简捷性和优越性.

目录

学位论文独创性声明及使用授权声明

摘要

前言

第一章：双圈图的树图的最大亏格

第二章：连通图的(邻接)树图的上可嵌入性

第三章：大次和条件图的上可嵌入性

第四章：一个三角等式的图论证法

参考文献

近期发表的论文

致谢