- 上一篇：带有反馈控制系统的两种群Lotka-Volterra合作系统模型生物数学合作系统的原理及
- 下一篇：我国CPI预测方法研究
摘 要: 对给定正整数 ，令 表示有 个三角形的扇， 为不含 作为子图的 阶图的最多边数，本文证明了当 时， ，这里 表示不超过 的最大整数.我们也给出了 的上下界.
毕业论文关键词: 图, 扇, Turán型问题58311
Abstract: For given positive integer , let be the fan with n triangles, and let be the maximum number of edges in all graphs of order not containing as a subgraph. In this paper we show that for , where is the greatest integer not exceeding . We also obtain upper and lower bound for .
Keywords: graph, fan, Turán’s problem
目 录
1 引言 4
2 的一般公式 5
3 的上下界估计 13
结论 17
参 考 文 献 18
致 谢 19
1 引言
本文中所有的图都是简单图，即既无环也无多重边的无向图. 我们用 表示图，其中 表示顶点集合， 表示边集合，在图 中，我们用 表示图 的边数, 表示顶点 关联的边的数目，即顶点次数或度，图 中顶点次数的最大值称为 的最大度，记为 .著名的 定理[1]断言
.图论中的Turán型问题是要确定不含给定图 为子图的 阶图的最多边数 . 1941年Turán[2]确定了 的一般公式,其中 是有 个顶点的完全图.特别地
完全图 如下所示：有关图的Turán型问题进展,见[3-9]，利用 式，本文证明了 ,
其中 是由两个有唯一公共点的三角形所构成的扇. 一般地，扇 是有一个公共顶点的 个三角形所构成的图，扇 如下所示：
本文还讨论了 的上下界.关于Turán型问题上界的确定，孙智宏老师给出了如下有用的引理：
引理1.1[9] 设 为自然数， 为给定图，则 .
下面介绍文中用到的其它记号. 我们用 表示点 生成的诱导子图， 表示点 的邻点集合,用 表示顶点二分类中分别有 个和 个顶点的完全二部图.
2 的一般公式论文网
由于完全图 与扇 相同，所以在考虑 的一般公式时我们需要借助公式 .
由于扇 为5阶图，故我们假定图 的阶 . 当 时，容易构造下图：
显然图 不含扇 为子图，且 ，故 .
现证 . 设图 是不含扇 为子图的5阶图，若 ，此时图 肯定不含扇 为子图，且
,从而 .现设 ，不妨设 , , ,即如下图所示：