图的上可嵌入性与独立顶点的度和

设G=（V,E）是2（或3）-边连通的简单图,独立数为α,围长为g,n=｜V｜.若下列条件之一成立：（1）独立数α＆lt;3g2（或6g-21）;（2）对G中任意含有m=3g2（或6g21）个顶点的独立集{v1,v2,...,vm}V,当g为偶数时,im=1dG（vi）n＋4（或n-11）;当g为奇数时,im=1dG（vi）n2（或n＋1）.则G是上可嵌入的.     

图的上可嵌入性

证明了一个连通无环图G如果能嵌入某个 (定向或不可定向 )曲面S上使得每个面的大小不超过 5 ,则G是上可嵌入的 .     

关于图的上可嵌入性的一个注记

任韩和李刚在图的最大亏格综述一文"Survey of maximum genus of graphs" [J East China NormUniv Natur Sci, Sep. 2010, No. 5, 1-13] 中,全面地阐述了近30 年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想:
猜想1 设G 为简单连通图, 且G 的每条边含在一个三角形K₃ 中, 则G 是上可嵌入的.
猜想2 设c 为任意的正数, 则存在一个自然数N(c), 使得对每一个图G, 若G 的点数n ≥ N(c), 且最小度δ(G) ≥ cn, 则G 是上可嵌入的.
本文的主要工作是否定上述两个猜想, 同时探讨上述猜想成立的条件且得了一些新结果, 并提出有关进一步研究的问题.     

上可嵌入性，边独立数与围长

结合边连通性,研究边独立数与上可嵌入性之间的关系,得到如下结果：设G为七一边连通图,围长为g,若α＇（G）≤（（k-1）^2＋2）[g/2]＋1-（-1）^g/2（（k-1）（k-2）＋1）-1,其中k=1,2,3,α＇（G）表示图G的边独立数,则G是上可嵌入的,且上界是最好的．这推广了相关结果．     

关于图的平面嵌入的一个上可嵌入性

本文证明了一个无环图Ｇ如果能嵌人在平面上使得每个面的次不超过５,则Ｇ是上可嵌入的,即当曲面为Ｓ平面时,证明了Ｒ．Ｎｅｄｅｌａ和Ｍ．Ｓｋｏｖｉｅｒａ［１］所提猜想成立．     

一类3-连通图的上可嵌入性

结合图的k-边形2-因子条件,确定了一类上可嵌入的3-连通图。     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

与顶点A-划分有关的上可嵌入图类

图G的顶点A-划分是指:G的顶点集划分{V1,V2,···,Vs},其中G[Vi](1≤i≤s)为多重完全图或多重完全二部图.文中结合图的顶点A-划分,顶点度及边连通性等条件确定了一些新的上可嵌入图类,从而将已有类似结果进行了推广,且完整地刻画了这类图的上可嵌入性情况.     

图的上可嵌入性的邻域条件

用NG（u）表示一个图G中任意点u的邻域集．本文主要证明了下述结果：设G是无环图,对G中任意相邻的点u和υ,即uυ∈E（G）,若如下两条件之一满足：（1）|NG(u)∩NG(υ)≥2;（2）G是2-点连通的图,且|NG(u)∩NG(υ)|≥1,则G是上可嵌入的．     

关于图的上可嵌入性的一个充分条件

本文主要证明:设G是一个(k+1)-边连通的n阶简单图,其围长为g,如果对G的任意独立集I(G)={v_i|1≤i≤k~2+2},k=0,1,2,均满足那么图G是上可嵌入的,而且下界是紧的.     

几类新的上可嵌入图

讨论了几类上可嵌入的边连通简单图,得到了如下结果:若G为简单连通图,且满足以下条件1)-3)之一:1)G为1-边连通的,且不含完全图K_3,α(G)≤3,2)G为2-边连通的,且不含完全图K_3,α(G)≤5,3)G为3-边连通的,且不含完全图K_3,α(G)≤10,则G是上可嵌入的,且在上述相应条件下,独立数上界都分别是最好的.     

关于点的度在modulo 4下等值的上可嵌入图类

结合 4-边形 2 -因子条件 ,确定了一类点的度在 modulo4下值为 0 ,1的上可嵌入图类 .从而综合已有的结果 ,较完整地刻划了这类图的上可嵌入性情况     

关于点的度在modulo下等值的上可嵌入图类

结合４－边形２－因子条件,确定了一类点的度在ｍｏｄｕｌｏ４下值为０,１的上可嵌入图类,从而综合已有的结果,较完整地刻划了这类图的上可嵌入性情况。     

点度与图的上可嵌入性

本文证明了:(1) 设G是2-连通简单图,且不含K_3,若对任意一对距离为2的点u,u,有max{d(u),d(u)}>n/3-1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/3-1"是不可达的;(2) 设G是3-连通简单图,若对任意依次相邻的三点u,u,W,有max{d(u),d(u),d(w)}≥n/6+1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/6+1"是最好的.     

关于图的上可嵌入性的一个新的邻域条件

用NG(u)表示一个图G中任意点u的邻域集．L∈{K1．3,Kl，3 e}，其中K1．3,K1，3 e是G的点导出子图．本文主要证明了下述结果:设G是简单图，对L中任意两个距离为2的点u和v，即dL(u,v)=2，都有|NG(u)∩NG(v)|≥2，则G是上可嵌入的．特别地，每个L—free图是上可嵌入的．     

图的上可嵌入性与非邻节点度和

本文得到了如下结果：令 Ｇ是一个 ２－边连通的（或３－边连通的）简单图，如果对于任何ｕｖ≠Ｅ（Ｇ）有则Ｇ是上可嵌入的．进而，这个下界是最好的．     

嵌入图的面度与最大亏格

利用图在曲面上的嵌入特征,特别是面的度的大小,研究图的最大亏格下界或上可嵌入性．     

与直径和围长有关的最大亏格的下界

本文证明了如下结果:设G为直径为d的简单图,若G的围长不小于d,则当d为不小于4的偶数时,有ξ(G)≤1,即G是上可嵌入的;当d为不小于3的奇数时,有ξ(G)≤2,即γM(G)≥1/2β(G)-1.     

图的上可嵌入性与独立数、非邻节点度和

本文研究了图的上可嵌入性与独立数、非邻节度点和之间的关系,得到了一些新的上可嵌入图类,推广了—个相关结果.从而,为进一步研究图的上可嵌入性提供了一定的理论基础.     

基本圈与图的曲面嵌入

本文研究图的基本圈与图在可定向曲面上的嵌入之间的关系．本文结果表明：一个图G可以嵌入到亏格至少为g的可定向曲面上的充分必要条件是：对于G中任意一个支撑树T,存在一个基本圈序列C1,C2,…,Q2g,使得对于每一个i：1≤i≤g,C2i-1∩C2i≠0．特别地,在T的β（G）个基本圈中有基本圈序列C1,C2…,Q2γM（G）,使得Qt-1∩C2t≠0对于每一个i：1≤i≤γM（G）成立．这里β（G）和γM（G）分别是G的Betti数和最大可定向亏格．这个结果的意义在于：我们可以从任意一个支撑树（可以具有任意奇连通分支数）出发去构造图在可定向曲面上的嵌入．这在本质上有别于Xuong与Liu在最大亏格方面的工作（即,从具有最小奇连通分支数的支撑树出发构造图嵌入）．事实上,这个结果在本质上同时推广了Xuong-Liu与Fu等在最大亏格方面的工作．作为这一结果的直接应用,本文得到以下结果：（1）提出了用于计算图的最大亏格的新条件,它尤其适用于计算具有特定边割（edge—cut）图的最大亏格．并得到一些新的与已知的著名结果（包括Huang在曲面嵌入图方面的工作）．（2）最大亏格问题可以归结为在基本相交图中求最大对集问题．结合Micali-Vazirani的一个有效算法,我们设计出了一个用于计算图的最大亏格的多项式算法,它的复杂度是O（（β（G））^5/2）,这一算法与Furst等人的算法相比更加直接、便于计算．