一些图类的上可嵌入性

《一些图类的上可嵌入性》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一些图类的上可嵌入性摘要本文主要研究拓扑图论的一个重要分支．图的上可嵌入性以及图的最大亏格的问题，其中图的最大亏格是刻划图在某个定向曲面上是否有二包腔嵌入的一个特征参数，而确定一类图的上可嵌入性就是要确定图的最大亏格．结合图的一个或几个参数，给出了若干新的上可嵌入图．具体内容如下；１．第三章结合图的距离及点度，根据不是上可嵌入的图的一个特征结构，并利用反证法，确定了几类新的上可嵌入图；２．第四章结合图的连通度和非邻节点度和条件，确定了几类新的上可嵌入图；３．第五章结合图的独立数和围长，确定了几类新的上可嵌入图，从而将已有这

2、方面的结果作了较大的推广，较完整地刻划了这些图类的上可嵌入情况．关键词：上可嵌入；最大亏格；Ｂｅｔｔｉ亏数；点度；连通度；独立数；围长．一些图类的上可嵌入性ＡＢＳＴＲＡＣＴＴｈｉｓｐａｐｅｒｃｈｉｅｆｌｙｓｔｕｄｉｅｓａ丑ｉｍｐｏｒｔａｎｔｓｕｂｊｅｃｔｉｎｔｏｐｏｌｏｇｉｃａｌｇｒａｐｈ－ｔｈｅｅｌ－ｂｅｄｄｉｎｇａｎｄｇｅｎｅｒａｏｆａｇｒａｐｈ，ａｎｄｔｈｅｍａｘｌｍｕｉｎｇｅｎｕｓｏｆｇｒａｐｈｉｓａｃｈａｒａｃｔｅｒｉｓｔｉｃｐａｒａｍｅｔｅｒ，ｗｈｉｃｈｄｅｔｅｒｍｉｎｅｓａｇｒａｐ

3、ｈｗｈｅｔｈｅｒｈａｓａ２－ｃｅｌｌｅｍｂｅｄｄｍｇｉｎａｃｅｒｔａｉｎｏｄ－ｅｎｔａｂｌｅｓｕｒｆａｃｅ．Ｗｈｉｌｅ．ｔｈｅｄｅｔｅｒｍｉｎａｔｉｏｎｏｆａｇｒａｐｈ＇ｕｐｐｅｒｅｍｂｅｄｄａｂｉｌｉｔｙｉ８ｔｏｄｅｔｅｒ－ｍｉｎｅａｇｒａｐｈ＇Ｕ１９１ｘｉｍｕｌ“ｇｅｎｕｓ．Ｃｏｍｂｉｎｉｎｇｏｎｅｏｒｍｏｒｅｐａｒａｍｅｔｅｒｓｏｆａｇｒａｐｈ，８０ｍｅｃｌａｓｓｅｓｏｆｎｅｗａｎｄｕｐｐｅｒｅｍｂｅｄｄａｂｌｅ舒８ｐｈ８ｗｉｌｌｂｅｇｉｖｅｎｉｎｔｈｅｔｈｅｓｉｓａ８ｆｏｌｌｏｗｓ：１．Ｄｅｔｅｒｍｉ

4、ｕｉａｇＳＯｍｅｄａｓｓｅｓｏｆｎｅｗａｎｄｕｐｐｅｒｅｍｂｅｄｄａｂｌｅｇｒａｐｈｓｉｎｃｈａｐｔｅｒｔｈｒｅｅｂｙｃｏｍｂｉｎｉｎｇｔｈｅｄｉｓｔａｎｃｅａｎｄｔｈｅｖｅｒｔｉｃｅｄｅｇｒｅｅ，ｆｕｒｔｈｅｒｍｏｒｅ，ｂａＳｉｓｉｎｇｏｎａｃｈａｒａｃｔｅｒｉｓｔｉｃｓｔｒｕｃｔｕｒｅｏｆａｕｎｕｐｐｅｒｅｍｂｅｄｄａｂｌｅｇｒａｐｈ；２．Ｄｅｔｅｒｍｉｎｉｎｇｓｏｍｅｄａｓｓｅｓｏｆｎｅｗａｎｄｕｐｐｅｒｅｍｂｅｄｄａｂｌｅｇｒａｐｈｓｉｎｃｈａｐｔｅｒｆｏｕｒｂｙｃｏｍｂｉｎｉｎｇｔｈｅｃｏｎｎｅ

5、ｃｔｅｄｄｅｇｒｅｅａｎｄｔｈｅｇｉｒｔｈ；３．Ｄｅｔｅｒｍｉｎｉｎｇｓｏｍｅｃｌａｓｓｅｓｏｆｎｅｗａｎｄｕｐｐｅｒｅｍｂｅｄｄａｂｌｅ字ａｐｈｓｉｎｃｈａｐｔｅｒｆｉｖｅｂｙｃｏｍｂｉｎｉｎｇｔｈｅｉｎｄｅｐｅｎｄｅｎｔ－ｎｕｍｂｅｒａｎｄＢｕｍｏｆｔｈｅｄｅｇｒｅｅｏｆｔｈｅｕｎｕｅｉｇｈ－ｂｏｒｅｄｖｅｒｔｅｘｅｓ．Ｔｈｕｓｉｔｇｅｎｅｒａｌｉｚｅｄｆｕｒｔｈｅｒｔｈｅｒｅｌａｔｉｖｅｒｅｓｕｌｔｓ，ａｎｄｃｈａｒａｃｔｅｒｉｚｅｄｅｌｌ－ｔｉｒｅｌｙｔｈｅｕｐｐｅｒｅｍｂｅｄｄｇ！ｂｉｌｉｔｙｏｆ

6、ｓｕｃｈｃｋｌ８８鹤ｏｆｇｒａｐｈｓ；Ｋｅｙｗｏｒｄｓ：ＵｐｐｅｒＥｍｂｅｄｄａｂｌｅ；ＭａｘｉｍｕｍＧｅｎｕｓ；ＢｅｔｔｉＤｅｆｉｃｉｅｎｃｙ；ＶｅｒｔｉｃｅＤｅ－ｇｒｅｅ；ＣｏｎｎｅｃｔｅｄＤｅｇｒ∞；Ｉｎｄｅｐｅｎｄｅｎｔ－ｎｕｍｂｅｒ；Ｇｉｒｔｈ．ＩＩｌ湖南师范大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的研究成果．除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品．对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明

7、．本人完全意识到本声明的法律后果由本人承担．学位敝储样：７稚吮叩年钥Ｊ日湖南师范大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅．本人授权湖南师范大学可以将学位论文的全部或部分内容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文．本学位论文属于１、保密口，在——年解密后适用本授权书．２、不保密口．（请在以上相应方框内打“

8、￣／”）作者签名日期：叼年６月７日日期：却泸６月／日括声以翩懿莒纰一些图类的上可嵌入性第一章引言图论是组合数学的一个主要组成部分，近几十年里，它已经发展成数学的一个重要分支．由于图论本身的魅力和其在信息社会中一些学科领域诸如计算机，运筹学，系统工程以及物理学，电子学，生物学，化学等方面的广泛应用，因