毕业论文

打赏
当前位置: 毕业论文 > 数学论文 >

扇Fn的Turán型问题

时间:2020-10-19 21:38来源:毕业论文
摘 要: 对给定正整数 ,令 表示有 个三角形的扇, 为不含 作为子图的 阶图的最多边数,本文证明了当 时, ,这里 表示不超过 的最大整数.我们也给出了 的上下界. 毕业论文关键词:

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

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

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

扇Fn的Turán型问题:http://www.751com.cn/shuxue/lunwen_63213.html
------分隔线----------------------------
推荐内容