一、边连通简单图的独立数与上可嵌入性（论文文献综述）
刘端凤[1]（2013）在《关于图的上可嵌入性研究》文中进行了进一步梳理图论是一门古老而又有趣的学科。它主要研究用某种方式联系起来的若干事物之间的二元或者多元的关系,其中包括拓扑图论、代数图论、化学图论、算法图论、网络图论、模糊图论等研究领域。它也是一门应用相当广泛的学科。在物理、化学、通讯科学、计算机技术以及信息技术等各种学科中都有应用。目前,拓扑图论逐渐地发展成为了一个非常活跃的图论分支。拓扑图论的发展极大地丰富了图论、拓扑学和组合学的内容。它主要是利用组合的各种方法来研究曲面的性状,进行曲面元的刻画。它的核心内容是研究图在曲面上的各种嵌入性质,特别是2-胞腔嵌入。因为一个图可以在多种不同的曲面上有多种可能的嵌入,所以研究图在曲面上嵌入的极值情况具有非常重要的意义。而图能上可嵌入到曲面上,就是指图的最大嵌入亏格取到它的上界的特殊情况,因而研究图的上可嵌入性也引起了广大图论学者的浓厚兴趣。关于图的上可嵌入性这一课题的研究,主要体现在两个方面：希望能找到一些图类,使得它们的最大亏格取到上界,从而图是上可嵌入的；对于非上可嵌入图,希望能找到它们的最大亏格的较好的下界。本论文主要利用图的一些不变量,如直径,围长,点的度,独立数,非邻节点的度和等,研究了图的上可嵌入性以及非上可嵌入图的最大亏格的下界。具体研究工作主要体现在以下几个方面：（1）研究了直径为3且不含3阶完全子图的图的上可嵌入性：若图G是一个直径为3的简单图,且G中不含3阶完全子图K3,则图G是上可嵌入的,也即ξ（G）≤1。这个结果与其他学者所做的结论一起,基本上完善了直径为3的图的上可嵌入性讨论。（2）给出了直径为4且不含3阶完全子图的图的最大亏格的紧下界：若G是直径为4的简单图,且G不含3阶完全子图K3则ξ（G）≤2。这改善了文献[79]的相关结果。（3）研究了直径为4且不含k-圈（k≤4）的图的上可嵌入性：设G是直径为4的简单图,若G不含k-圈（k≤4）,则ξ（G）≤1,也即G是上可嵌入的。这与（2）一起,比较完整地研究了直径为4的图的上可嵌入性。（4）用多个非邻节点度和以及独立数研究了一类半双图和单瓣图的上可嵌入性：设G是一个阶为,n的2-边连通半双图,若G满足条件（a）或（b）：（a） α（G）≤2；（b）α（G）≥3,且对于任何彼此不相邻的三个顶点ui,（i=1,2,3）都有则G是上可嵌入的。而且条件（b）中的下界是最好的。这改善并推广了文献[88]的相关结果。对于阶为n的2-边连通单瓣图的上可嵌入性,相对于半双图来说,要复杂一些,我们也得到了类似的结果。（5）研究了一类有环的非简单图和它的补图的上可嵌入性：设G是连通图,若G满足条件（a）或（b）：（a）无环；（b）有环,但任意一个带环的顶点w,w带的环的个数都是偶数。则G或者Gc是上可嵌入的。而文献[82]只考虑了无环图和它的补图的上可嵌入性。（6）利用图的一些其他参数,比如点的度,2-因子等,研究图的上可嵌入性,得到了一些新的上可嵌入图类。推广和补充了相关结果。
李刚[2]（2011）在《图的最大亏格与三类图的1-因子数目》文中研究表明本文主要研究了两个问题：图的最大亏格以及三类图的1-因子计数.本文第一部分是关于图的最大亏格的综述.图的最大亏格问题一直以来都是图嵌入理论中的一个重要问题,本文综述了近30年来关于图的最大亏格,以及它与其他不变量之间关系的重要研究和进展,其中包括最大亏格与图的连通性,图的直径,图的染色数和图的2-因子之间的关系,最大亏格嵌入数目以及最大亏格与嵌入图等方面,并就这些方面给出了自己的一些看法.本文第二部分研究了三类图的1-因子（又称为完美匹配）计数问题.图的1-因子计数问题是匹配理论研究中的一个重要课题Lovasz和Plummer就曾提出关于1-因子计数的一个猜想：任意的2-边连通3-正则图都有指数多个1-因子.另外,1-因子理论在很多领域也有很强的应用背景比如物理学和化学.但是,一般图的1-因子计数问题已经被证明了是NP-困难的,所以一般考虑一些特殊图的1-因子计数.本文用划分,求和,递归的方法分别给出了三类特殊图（本文称作L2n,C（2n,2）和O3.2n-1）的1-因子数目的计算公式,从而验证了Lovasz和Plummer的猜想在这三类图上的正确性.
吕胜祥[3]（2010）在《关于图的最大亏格与其它不变量》文中指出图在曲面上的嵌入起源于地图着色定理的证明.这里,曲面S就是无边缘的紧2-维闭流形,分为可定向曲面与不可定向曲面[6].连通图G在曲面s上的2-胞腔嵌入,简称为嵌入,是指存在一个1-1连续映射φ：G→S使得S-φ（G）的每个连通分支都同胚于一个开圆盘.图G的最小亏格,γ（G）,就是最小的整数n使得图G能嵌入到亏格为n的可定向曲面Sn.图G的最大亏格,γM（G）,就是最大的整数n使得图G能嵌入到亏格为n的可定向曲面Sn.1966年,Duke[12]得到了可定向曲面嵌入的插值定理：若图G可嵌入到可定向曲面Sn和Sm（n≤m）,则对任意的整数g,n≤g≤m,图G可嵌入到可定向曲面Sg.因此,图G的最大和最小亏格确定了图G能嵌入的全部可定向曲面.相似的,可定义最大不可定向亏格和最小不可定向亏格.关于图G的最大不可定向亏格γM（G）,刘彦佩教授[36],Ringel[50]以及Stahl[59]分别独立地证明了于是,我们只需考虑图在可定向曲面上的最大亏格.因为图G在任意曲面上的嵌入至少有一个面,由Euler公式易得其中,β（G）=ε（G）-ν（G）+1称为图G的Betti数；[x]表示不超过x的最大整数.若γM（G）=[β（G）/2],则称图G是上可嵌入的.本论文主要结合图的一些不变量,如最小度,围长,顶点数,独立数,顶点的度和等,研究了图的上可嵌入性以及图的最大亏格的下界,并给出了非上可嵌入的3-正则图的结构特征.具体分为以下七章.第一章,首先对图在曲面上嵌入的研究背景及发展作了简单介绍.其次,给出了图论的一些基本概念和术语以及图的最大亏格的一些基本性质.第二章,结合图的最小度和围长,从研究图的给定子图的顶点数出发,我们得到了图的上可嵌入性与顶点数之间的关系.第三章,结合图的最小度和围长,给出了非上可嵌入连通图的最大亏格的新下界.第四章,结合图的围长,从研究图的给定子图内相邻顶点的度和出发,得到了图的上可嵌入性与相邻顶点度和的关系.第五章,结合图的最小度和围长,从研究图的给定子图内独立数,非相邻顶点的度和出发,得到了图的上可嵌入性与独立数,非相邻顶点的度和之间的关系.第六章,研究了非上可嵌入的2-边连通3-正则图的结构,补充了文献[28]中关于上可嵌入的2-边连通3-正则图的结构.第七章,提出了一些进一步研究的问题,如计算图的最大亏格嵌入的个数,研究图的相对最大亏格,应用联树方法研究图的最大亏格等.
蔡俊亮,董广华,刘彦佩[4]（2010）在《关于图的上可嵌入性的一个充分条件》文中研究说明本文主要证明:设G是一个（k+1）-边连通的n阶简单图,其围长为g,如果对G的任意独立集I（G）={vi|1≤i≤k2+2},k=0,1,2,均满足那么图G是上可嵌入的,而且下界是紧的.
吕胜祥,刘彦佩[5]（2009）在《图的上可嵌入性与独立顶点的度和》文中提出设G=（V,E）是2（或3）-边连通的简单图,独立数为α,围长为g,n=|V|.若下列条件之一成立:（1）独立数α<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是上可嵌入的.
张启明,黄元秋,任俊峰[6]（2009）在《点度与图的上可嵌入性》文中研究说明本文证明了:（1）设G是2-连通简单图,且不含K3,若对任意一对距离为2的点u,v,有max{d（u）,d（v）}>n/3-1,其中n=|V（G）|,则G是上可嵌入的,且条件中不等式的界"n/3-1"是不可达的;（2）设G是3-连通简单图,若对任意依次相邻的三点u,u,w,有max{d（u）,d（v）,d（w）}（?）n/6+1,其中n=|V（G）|,则G是上可嵌入的,且条件中不等式的界"n/6+1"是最好的.
李浩玲[7]（2009）在《图的生成树和最大亏格》文中研究指明亏格是图的一个拓扑不变量.根据Duke关于图亏格的内插定理,最大亏格的界定对于研究图的亏格分布具有重要意义.本文主要研究一个图的生成树与图的最大亏格之间的关系以及它在图的上可嵌入性方面的应用.其主要结果如下:（1）通过图G的生成树变换,我们可以改变一个生成树T与其余树G-E（T）的连通分支的奇偶性.由此,给出了黄元秋和刘彦佩定理的一个新的证明.特别地,设T为图G的一棵最优树,记G’是在G中加入一对关于T相邻的边e’和e”所得到的图.则ξ（G’）≤ξ（G）.从而γM（G’）≥γM（G）+1;特别地,若G是上可嵌入的,则G’也是上可嵌入的.结合上面的结论,我们给出了由最优树所确定的基本圈全体的一个性质:基本圈全体可以被分解成两部分:其一,{C1,C2,C3,C4,…,C2k-1,C2k),k=γM（G）,C2k-1∩C2i≠（?）,（1≤i≤k）;其二,{C2k+1,C2k+2,…,C2k+s),s=ξ（G）,（这里ξ（G）为图G的Betti亏数）,且任意两个基本圈不相交.（2）借助于生成树变换理论,我们得到一个关于局部连通图G的最优树奇连通分支的遍历性结果:对于局部连通图G,若ξ（G）=1,则给定顶点x∈V（G）,一定存在一棵最优树T使得x属于G关于T的奇连通分支.在此基础上,给出LNebesk（?）定理的一个新证明.将其推广,我们得到一些新的上可嵌入图类,比如:G1,G2是局部连通图,S={e1,e2,…,ek},（k≥2）是一边集,在G1,G2中加入边集S,使得S中的每条边的两个端点分别属于G1,G2得到的图G是上可嵌入的,置换图和由两个圈构成的广义Petersen图也是上可嵌入的.
欧阳章东,任俊峰,黄元秋[8]（2009）在《最大亏格、点度和围长》文中指出用g（G）和δ（G）分别表示一个图G的围长和顶点最小度.ξ（G）为图G的Betii亏数,主要证明了以下2个结果1)设G为k-边连通简单图,若对G中任意圈C,存在点x∈C满足dG（x）>（|V（G）|）/（（k-1）2+2）+k-g（G）+2,k=1,2,3,则G是上可嵌入的.且不等式的下界是最好的; 2)设G为k-边连通简单图,则ξ（G）≤（?）其中m=（|V（G）|g（G）-6）/（g（G）2+（δ（G）-2）g（G）-4′）且不等式的上界是可达的.进而得到了最大亏格一个比较好的下界.
欧阳章东,唐玲,黄元秋[9]（2009）在《上可嵌入性，边独立数与围长》文中进行了进一步梳理结合边连通性,研究边独立数与上可嵌入性之间的关系,得到如下结果:设G为k-边连通图,围长为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是上可嵌入的,且上界是最好的.这推广了相关结果.
张启明,黄元秋,欧阳章东[10]（2008）在《几类新的上可嵌入图》文中认为讨论了几类上可嵌入的边连通简单图,得到了如下结果:若G为简单连通图,且满足以下条件1)-3)之一:1)G为1-边连通的,且不含完全图K3,α（G）≤3,2)G为2-边连通的,且不含完全图K3,α（G）≤5,3)G为3-边连通的,且不含完全图K3,α（G）≤10,则G是上可嵌入的,且在上述相应条件下,独立数上界都分别是最好的.
二、边连通简单图的独立数与上可嵌入性（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、边连通简单图的独立数与上可嵌入性（论文提纲范文）
（1）关于图的上可嵌入性研究（论文提纲范文）
| 摘要 |
| Abstract |
| 目录 |
| 1 绪论 |
| 1.1 研究背景 |
| 1.2 本文主要内容安排 |
| 2 图的基本概念和基本定理 |
| 2.1 基本概念 |
| 2.2 基本定理 |
| 3 图的上可嵌入性与直径 |
| 3.1 直径为2或3的图的上可嵌入性 |
| 3.2 直径为4的图的最大亏格下界 |
| 3.3 直径为4的图的上可嵌入性 |
| 3.4 直径为d的图的最大亏格下界 |
| 3.5 本章小结 |
| 4 非简单图的上可嵌人性 |
| 4.1 半双图的上可嵌入性与独立数、非邻节点度和 |
| 4.2 单瓣图的上可嵌入性与独立数、非邻节点度和 |
| 4.3 图G和它的补图G~c的上可嵌人性 |
| 4.4 本章小结 |
| 5 图的上可嵌入性与其它参数 |
| 5.1 偶图的上可嵌入性 |
| 5.2 图的上可嵌入性与2-因子 |
| 5.3 图的上可嵌入性与顶点划分 |
| 5.4 局部连通图的上可嵌入性 |
| 5.5 本章小结 |
| 6 总结和展望 |
| 6.1 本文工作总结 |
| 6.2 进一步研究工作展望 |
| 参考文献 |
| 附录 |
| 致谢 |
| 攻读博士学位期间主要的研究成果 |
| 参与的科研项目 |
（2）图的最大亏格与三类图的1-因子数目（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 引言 |
| 1.1 图的最大亏格研究背景和基本定理 |
| 1.2 图的1-因子数目研究的背景和基本概念 |
| 第二章 图的最大亏格 |
| 2.1 最大亏格和连通度 |
| 2.2 最大亏格与直径 |
| 2.3 最大亏格与围长,匹配和独立数 |
| 2.4 最大亏格与色数 |
| 2.5 最大亏格与2-因子 |
| 2.6 最大亏格与嵌入图 |
| 2.7 图的最大亏格嵌入数目 |
| 第三章 三类图的1-因子数目 |
| 3.1 图L_(2n)的1-因子数目 |
| 3.2 图C(2n,-2)的1-因子数目 |
| 3.3 图O_(3.2n-1)的1-因子数目 |
| 3.4 总结 |
| 参考文献 |
| 后记 |
（3）关于图的最大亏格与其它不变量（论文提纲范文）
| 致谢 |
| 中文摘要 |
| ABSTRACT |
| 目录 |
| 符号说明 |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.2 相关概念与性质 |
| 第二章 图的上可嵌入性与顶点数 |
| 2.1 主要引理 |
| 2.2 主要结论 |
| 第三章 最大亏格的下界与最小度和围长 |
| 3.1 简单图的最大亏格的下界 |
| 3.2 非简单图的最大亏格的下界 |
| 第四章 上可嵌入性与相邻顶点的度和 |
| 4.1 主要引理 |
| 4.2 主要结论 |
| 第五章 上可嵌入性与独立集 |
| 5.1 上可嵌入性与独立顶点度和 |
| 5.2 上可嵌入性与独立数及不相邻顶点度和 |
| 第六章 非上可嵌入的3-正则图的结构 |
| 6.1 主要引理 |
| 6.2 主要结论 |
| 第七章 进一步研究计划 |
| 参考文献 |
| 索引 |
| 作者简历 |
| 学位论文数据集 |
（4）关于图的上可嵌入性的一个充分条件（论文提纲范文）
| 1 引言 |
| 2 若干引理 |
| 3 主要结果 |
（5）图的上可嵌入性与独立顶点的度和（论文提纲范文）
| 1 引言 |
| 2 基本引理 |
| 3 定理的证明 |
（6）点度与图的上可嵌入性（论文提纲范文）
| 1 引言 |
| 2 有关术语和引理 |
| 3 定理的证明 |
（7）图的生成树和最大亏格（论文提纲范文）
| 摘要 |
| Abstract |
| 前言 |
| 第一章 预备知识 |
| 1.1 图的基本概念 |
| 1.2 曲面及其性质 |
| 1.3 基本定理 |
| 第二章 最优树确定的基本圈性质 |
| 2.1 有关引理和结论 |
| 2.2 主要结果 |
| 第三章 L.Nebesk(?)定理的新证明及其推广 |
| 3.1 L.Nebesk(?)定理的新证明 |
| 3.2 L.Nebesk(?)定理的推广 |
| 硕士期间完成发表论文 |
| 参考文献 |
| 致谢 |
（8）最大亏格、点度和围长（论文提纲范文）
| 1 引言 |
| 2 有关术语和引理 |
| 3 定理及其证明 |
（10）几类新的上可嵌入图（论文提纲范文）
| 1 引言 |
| 2 引理及其证明 |
| 3 主要结果及其证明 |
四、边连通简单图的独立数与上可嵌入性（论文参考文献）
- [1]关于图的上可嵌入性研究[D]. 刘端凤. 中南大学, 2013(02)
- [2]图的最大亏格与三类图的1-因子数目[D]. 李刚. 华东师范大学, 2011(09)
- [3]关于图的最大亏格与其它不变量[D]. 吕胜祥. 北京交通大学, 2010(07)
- [4]关于图的上可嵌入性的一个充分条件[J]. 蔡俊亮,董广华,刘彦佩. 中国科学:数学, 2010(02)
- [5]图的上可嵌入性与独立顶点的度和[J]. 吕胜祥,刘彦佩. 中国科学（A辑:数学）, 2009(10)
- [6]点度与图的上可嵌入性[J]. 张启明,黄元秋,任俊峰. 应用数学学报, 2009(05)
- [7]图的生成树和最大亏格[D]. 李浩玲. 华东师范大学, 2009(12)
- [8]最大亏格、点度和围长[J]. 欧阳章东,任俊峰,黄元秋. 系统科学与数学, 2009(03)
- [9]上可嵌入性，边独立数与围长[J]. 欧阳章东,唐玲,黄元秋. 中国科学（A辑:数学）, 2009(02)
- [10]几类新的上可嵌入图[J]. 张启明,黄元秋,欧阳章东. 系统科学与数学, 2008(12)