摘要：设 是8个顶点的轮， 表示不含 作为子图的 阶图最多边数，本文证明了  .

毕业论文关键词：图，轮，Turán型问题65451

Abstract:Let   be the wheel with 8 vertices,  and let   be the maximal number of edges in all graphs of order   not containing   as a subgraph. In this paper, we prove that  .

Keywards: graph, wheel, Turan’s problem

目录

1 前言 4

2 主要结果及其证明 5

结论 16

参考文献 17

致谢 18

1 前言

本文中所有的图皆为简单图，设 是一个非空有限集合，其中的元素称为顶点或点。若另一有限集合 中每个元素都同 中一个元素相对应，则称 为一个图，其中 为顶点集合， 为边集合， 中每个元素称为图的一条边，并且记 为图 的边数。设 为图 的一个顶点，称 中与 关联的边的数目为 在 中的次数或度，记为 .图 中顶点次数的最大值称为 的最大度，记为 .本文中 标记为 个顶点的圈构成的图，那么轮 就是在圈 中增加一个顶点 ，且顶点 与圈 中的所有顶点都相邻。

对给定图 ， 是不含 作为子图的 阶图的最多边数，Turán型问题就是估计 的值。1941年Turán（[4]）给出了 的公式，这里 为 个顶点的完全图，设 则

 ,

特别当 时，

 ,

这里 为不超过 的最大整数。由于 即为 ，故

 .

2012年A.A.Alrhayyel, A.M.M.Jaradat, M.M.M.Jaradat和M.S.A.Bataineh([2])给出了 与 的如下公式：当 时，如果 ， 或 ，则

 ,

当 时，使

 .

2013年Dzido（[1]）证明了对所有的正整数 ，当 ，且 时

 ,

根据孙智宏老师最近给出的猜想：对所有的正整数 ，当 时，

 ,

本文主要对 验证孙老师的猜想。

引理1([5])：设 为正整数， ，则来.自/751·论|文-网·www.751com.cn/

 ,

由于 不包含 作为子图，且 ，故

 ,

由此

 .

引理2([3])：设 为正整数，当 时，若 ，则 ，从而

 ，

若 ，则

 .

2 主要结果及其证明

定理1： .文献综述

证明  设 是9阶图， ，因 中心次数为7，故当 时， 不含 为子图，此时

 ,

从而

 .

若 ，考虑 ：

当 为8-正则图时， 为9个顶点完全图（如下图 ）， ，此时 包含 为子图。

轮Wn的Turán型问题:http://www.751com.cn/shuxue/lunwen_73095.html