论文部分内容阅读
稠密图的图分解问题一直受到国内外广大学者的关注,20世纪时期Wilson得出一个基本定理:对于任意给定的图F,任意充分大的F-可分团G都可以分解出一些边不相交的且与图F同构的子图,即当可分图G的点度为n-1时存在F-分解.本文是在Barber等人得出稠密图进行r-正则图分解的点度条件基础上,考虑对于点数为n且充分大的(△-)-可分图G进行非正规图分解的点度条件,得出当其最小点度满足δ(G)≥3/4n+o(n)时,存在着(△-)-分解((△-)图记为(K3+e)). 本文的结构组织如下: 第一章,简要介绍稠密图分解的研究现状和背景、给出图分解的相关的定义以及简述本文所做的的重要结果. 第二章,构造图F-吸收子(absorber)以及考虑图G中存在F-吸收子(absorber)的点度要求. 第三章,在证明图G存在F-吸收子的条件下,证明图G存在图F几乎可分解,进而证明图G存在F-分解. 第四章,拓展推广,研究在(△-)图的基础上进行加边,找出其存在图分解的点度的必要条件以及猜想其存在图分解的点度的最小下界.