关于一些特殊图的上可嵌入性研究

摘要

自从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]分别给出了不同形式的充要条件;黄元秋和刘彦佩[18]从另一相反角度出发，提供了一个关于不是上可嵌入图的充要条件.由此充要条件，本文主要对一些满足特殊条件的图的上可嵌入性进行专门研究，共分为五章. 在第一章中：集中探讨范条件图的上可嵌入性.设G是2点连通图，若对任一对使d(u，v)=2的点u，v，满足max{d(u)，d(v)｝≥n/2(其中n=｜V(G)｜)，则称G是满足范条件的图；我们证明了范条件图是上可嵌入的.在第二章中：集中探讨大次和条件图的上可嵌入性.设G是k点连通图，若对任一{x1，x2，…，xk+1}-独立集均有d(x1)+d(x2)+…+d(xk+1)≥n-k(n=｜V(G)｜)，则称G是满足大次和条件的图;我们证明了2类大次和条件图是上可嵌入的.在第三章中：集中探讨G的立方图G3的上可嵌入性.设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是上可嵌入的. 在第四章中：集中探讨特殊二部图的上可嵌入性.我们证明下述结果：(1)设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}，则G3是上可嵌入的；(2)设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-正则图的叶子数与最大亏格rM(G)之间的关系并给出3-正则图最大亏格的一个计算公式：rM(G)=1/2[l(T)+pα-pβ]，这里T是Xuong树，l(T)是T的叶子数，pα，pβ分别是G-E(T)中偶长路数与奇长圈数.

目录

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

摘要

前言

第一章：范条件图的上可嵌入性

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

第三章：G的立方图G3的上可嵌入性

第四章：特殊二部图的上可嵌入性

第五章：3-正则图最大亏格的一个计算公式

参考文献

近期论文发表及参与的课题

致谢