摘要:设 是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个顶点完全图(如下图 ), ,此时 包含 为子图。

上一篇:瑞利分布的特征
下一篇:运输问题在城市居民蔬菜供应方面应用

浅谈中学数学函数最值问题的求解方法

基于决策树算法的篮球联赛预测

数形结合在中学数学中的...

浙江省工业企业发展的因子分析

中美小学数学课堂教学的比较

杭州历年中考三角形的题型分析

论数形结合在中学数学教育中的应用

张洁小说《无字》中的女性意识

安康汉江网讯

网络语言“XX体”研究

我国风险投资的发展现状问题及对策分析

ASP.net+sqlserver企业设备管理系统设计与开发

老年2型糖尿病患者运动疗...

互联网教育”变革路径研究进展【7972字】

LiMn1-xFexPO4正极材料合成及充放电性能研究

新課改下小學语文洧效阅...

麦秸秆还田和沼液灌溉对...