几类图的弱饱和数的研究

发布时间：2017-12-11 12:01

  本文关键词：几类图的弱饱和数的研究

  更多相关文章： 饱和图 弱饱和数 多重图 完全二部图 完全图 补图

【摘要】：给定一个图F,图G是关于图F的n阶饱和图,如果|V(G)|=n,并且在G中没有与图F同构的子图,但是对于图G的补图G中的任意边e,在G+e中有一个与图F同构的子图。用SAT(n,F)表示图F的n阶饱和图的集合,集合SAT(n,F)中图的最小边数称为饱和数,记作sat(n,F)。图G是关于图F的n阶弱饱和图,如果|V(G)|=n,且在G中没有与图F同构的子图,但是对于图G的补图G中的所有边存在一个排序,按这个排序在图G上依次加G中所有边,每次加一条边,可以产生一个包含所加边且与图F同构的子图,持续这个过程,直到我们得到一个完全图。用wSAT(n,F)表示图F的n阶弱饱和图的集合,集合wSAT(n,F)中图的最小边数称为弱饱和数,记作wsat(n,F)。相比较已经取得较完整理论体系的极图理论的研究,图的弱饱和数的研究还没有得到比较好的一般性的结论。一种获得图弱饱和数一般性结论的方法是：研究几类具体图的弱饱和数,确定这些图达到弱饱和数时的性质,然后推广到一般情况。本文主要研究了几类图的弱饱和数,主要包括以下四部分：第一章介绍了图G的饱和数与弱饱和数的概念,国内外研究现状,本文所用的重要符号及本文主要研究结果。第二章给出了wsat(n,Kt－K1,m),完全回答了[11]中的问题3：对于图Kt－K1,m,2≤ mt－1, wsat(n,Kt－K1,m)=n(t－m－2)－t2－(2m+3)t/2－(m+1)是否成立。又给出了wsat(n,Kt－K2)和wsat(n,Kt－2K2),部分回答了[11]中的问题4：对于图Kt－sK2,1≤ st－1/2, wsat(n,Kt－sK2)=(t－1/2)－s+(n－t+1)(t－3)是否成立。还推广了[12]中方法,给出了wsat(n,k(K5－K2))、wsat(n,k(Kt－K2))和wsat(n,k(Kt－K1,m)),部分回答了[12]中的问题1：当k≥2,n充分大时,什么样的连通图G能够满足wsat(n,kG)=wsat(n,G)+k－1。第三章给出了wsat(n,kpUKq)(p≤q),这是对wsat(n,kKt)[12]的推广。通过改进[11]中方法,又给出了wsat(n,K2,6)和wsat(n,K2,t),部分回答了论文[11]中的问题2：对于最小度为δ的图F,|V(F)|=p,|E(F)|=q,n≥p,当图F满足什么性质时才能使q-1+(δ-1)(n－p)≤wsat(n,F)≤(p－1/2)+(δ－1)(n－p+1)成立。第四章给出了wsat(n,K3,4)和wsat(n,Kt,t+1)的上界,部分回答了论文[11]中的问题2,并提出了一个公开问题。
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】

中国期刊全文数据库 前10条

1 王殿军;完全图圈分解的一种新方法[J];高校应用数学学报A辑(中文版);1993年04期

2 邓觐超,佟玉凤;有关完全图的算法及实现技术[J];烟台大学学报(自然科学与工程版);1997年03期

3 张文军;;完全图的最小6-圈覆盖和8-圈覆盖[J];山东理工大学学报(自然科学版);2008年04期

4 O赐蜢，

本文编号：1278356