摘 要: 设 F3 是三个有公共顶点而边不相交的三角形构成的扇，exp; F3 为不含 F3 作为子 图的 p 阶图最多边数，本文证明了 ex7; F3 17 ，ex8; F3 20 ，ex9; F3 25 ，ex10; F3 30 与 ex11; F3 36 ，并给出了 exp; F3 一般公式的猜想.70909

毕业论文关键词: 图, 扇, Turán 型问题

Abstract: Let F3      be the fan with three edge-disjoint triangles having a common vertex ,and let

be the maximum number of edges in all graphs of order   p   not containing

subgraph. In this paper we show that

Keywords: graph, fan, Turán’s problem

目 录

1 引言 4

2 主要结果及其证明 5

3 exp; F3 一般公式的猜想 19

结论 20

参考文献 21

1 引言

本文中所有的图都是简单图. 我们用 G V G, EG表示图，其中V G表示 顶点集合，EG表示边集合.在图 G 中，我们用 eG表示图 G 的边数，d v表示 顶点 v 关联的边的数目，即顶点次数或度，图 G 中顶点次数的最大值称为 G 的最 大度，记为 G.著名的 Euler 定理[1]给出

图论中的 Turán 型问题是要确定不含指定图 H 为子图的 p 阶图的最多边数

exp; H . 1941 年 Turán[2]确定了 exp; K 完全图.特别地

的一般公式，其中 Kn 是有 n 个顶点的文献综述

有关图的 Turán 型问题进展,见[4-9].

一般地，对 n 2 为自然数，扇 Fn 是有一个公共顶点的 n 个三角形所构成的 图，扇 F3 如下所示：

在[3]中陈彦蓉证明了

本 文 证 明 了 : ex7; F3 17 , ex8; F3 20 ， ex9; F3 25 ， ex10; F3 30 与

ex11; F3 36 ，并给出了 exp; F3 一般公式的猜想.关于 Turán 型问题上界的确 定，孙智宏老师给出了如下有用的引理：

引理 1.1[4] 设 p  2 为自然数， L 为给定图，则 ex p; L  



下面介绍文中用到的其它记号.我们用 Gv1 , v2 ,vn 表示点 v1 , v2 ,vn 生成的 诱导子图，用 Km,n 表示顶点二分类中分别有 m 个和 n 个顶点的完全二部图，用

v0 表示点 v0  的邻点集合.

2 主要结果及其证明

定理 2.1

ex7; F3 17 .

证: 容易构造下图 G1 :

易见图 G1 是不含扇 F3 为子图的 7 阶图，且 eG1   17 , 故

ex(7; F3 )  eG1   17 .

现设图 G 是不含扇 F3 为子图的 7 阶图，V G  v0 , v1 , v2 , v3 , v4 , v5 , v6 ,我们通过对

G分类讨论验证 eG17 .

（a） G5 .图 G 肯定不含扇 F3 为子图，由 Euler 定理知

2e(G) d v7 5 35 ,

vV G 

从而

eG17 17.5 .

(b) G6 .不妨设 v0 V G, d v0 G6 , v0 v1 , v2 , v3 , v4 , v5 , v6 , 即如下图所示：