摘  要: 对给定正整数 ，令 表示有 个三角形的扇， 为不含 作为子图的 阶图的最多边数，本文证明了当 时， ，这里 表示不超过 的最大整数.我们也给出了 的上下界.

毕业论文关键词: 图, 扇, 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阶图，若 ，此时图 肯定不含扇 为子图，且

 ,从而 .现设 ，不妨设 , , ,即如下图所示：