毕业论文

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

轮Wn的Turán型问题

时间:2021-04-12 19:44来源:毕业论文
设 是8个顶点的轮, 表示不含 作为子图的 阶图最多边数,本文轮Wn的Turán型问题证明了

摘要:设 是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]):设 为正整数, ,则来.自/优尔·论|文-网·www.youerw.com/

 ,

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

 ,

由此

 .

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

 ,

若 ,则

 .

2 主要结果及其证明

定理1: .文献综述

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

 ,

从而

 .

若 ,考虑 :

当 为8-正则图时, 为9个顶点完全图(如下图 ), ,此时 包含 为子图。

轮Wn的Turán型问题:http://www.youerw.com/shuxue/lunwen_73095.html
------分隔线----------------------------
推荐内容