附加二部图条件的Erd（?）s-Sós猜想的若干讨论

论文摘要

极图理论中著名的Erd（?）s-Sós猜想指出,对于n阶图G,若其边数大于n（k-2）/2,则所有k阶树都是G的子图。基于树是连通二部图的事实,本文考虑对图G附加二部图条件。在附加二部图条件下,本文证明了如下几类树是图G的子图:（1）直径为5的树;（2）最大度大于等于「k-1/2」的树;（3）二部划分几乎平衡的树;（4）直径大于等于k-4的树。此外,本文证明了在附加二部图条件下,当k≤12时,Erd（?）s-Sós猜想成立。在二部图条件下还有一个有趣的发现:若所有直径为2m的k阶树是G的子图,则所有直径为2m+1的k阶树也是G的子图。这个发现告诉我们在此条件下只须考虑直径为偶数的树即可。相比于Erd（?）s-Sós猜想的已知结果,本文在附加二部图条件下得到了更强的结果。本文所使用的主要方法是图的嵌入,特别是固定某些顶点的嵌入。使用这一方法的动机来源于对图G的观察:如果一个图的平均度大于k-2,那么它包含一个平均度大于k-2的子图,且这个子图的最小度大于等于「k/2」。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
•   1.1 问题背景
•   1.2 国内外研究现状
•     1.2.1 对图G附加条件
•     1.2.2 对特定的树进行讨论
•     1.2.3 对特定的n和k进行讨论
•   1.3 Erd（?）s-Sós猜想的几个变形猜想
•   1.4 内容简介
• 第2章 预备知识
•   2.1 符号和定义
•   2.2 基本结果
•   2.3 极图理论
• 第3章 嵌入方法的应用
•   3.1 对图G的讨论
•   3.2 嵌入方法与图的最小度条件
• n,k'>  3.3 嵌入方法与图S_n,k
• 第4章 对二部图的讨论
•   4.1 对图附加二部条件
•   4.2 二部条件下的若干引理
•   4.3 二部条件下的新结果
•   4.4 二部条件下关于k的取值的结果
•   4.5 本章小结
• 第5章 总结
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果

文章来源

类型: 硕士论文

作者: 吕晨晖

导师: 侯新民

关键词: 猜想,二部图,嵌入,最小度

来源: 中国科学技术大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 中国科学技术大学

分类号: O157.5

总页数: 38

文件大小: 1679K

下载量: 8