1. 引言
设
是一个简单无向图,其中V和E分别表示图G的顶点集和边集。用
表示图G的边集大小。令H是一个图,若
,
,则称H是G的一个子图。令
表示由一些图组成的集族,如果对任意的
,图G都不包含F作为子图,那么称图G是
-禁止图。Turán数
定义为n个顶点的
-禁止图中的最大边数。如果集族
仅包含一个简单图F,则我们可以将
简写为
。关于Turán数现在已经有大量的研究,详见相关文献 [1] - [12] 。
设
和
是图G的两个不相交的子图,
表示
和
的并图,其顶点集为
,边集为
。
表示
和
的联图,其顶点集为
,边集为
。
表示n个顶点的完全图,
表示n个顶点的空图。令
表示n个顶点的Turán图,即含有n个顶点的完全r部图且每个部集的大小为
或
。
1907年,Mantel [7] 证明了以下定理:
定理1.1. 若G是n个顶点的
-禁止图,则
同时,二部Turán图是唯一的可以达到边极值的图。
1941年,Turán [9] 证明了Turán图是唯一一个达到最大边数的
禁止图。
定理1.2.对于
,
,
Erdős和Gallai [3] 在1959年证明了
的图兰数上界。
定理1.3. 若
,则
当
整除n时,
个点不交的
的并是取到等号的一个图。
Faudree和Schelp [13] 以及Kopylov [14] 确定了对于任意的n的值,
的精确值,并且刻画了对应的极图。
定理1.4. 令
,
,且
,则
相应的极图为
,即q个点不交的
和一个
的并。当
是偶数且同时r是
或者
,极图为
个点不交的
和一个H的并,其中H为
。
Erdős和Gallai [3] 在1959年证明了
的图兰数上界。
定理1.5. 对于
,
当
整除
时,
个
共用一个点的图是取到等号的一个图。
Woodall [15] 在1976年以及Kopylov [14] 在1977年独立地证明了
的精确值。
定理1.6. 令
,
,且
,
,则
2015年,Füredi和Gunderson [16] 研究了奇圈的图兰数,并且给出了以下定理:
定理1.7. 对
,
,
其中,当
,且
,
,s和r都是整数时,
在本文中,我们研究了n个点的
-禁止图,以及当
为奇数时
-禁止图的最大边数。
定理1.8. 对于
,则
注意到当
时,根据定理1.7和1.8可以推出
。显然,
是一个
-禁止图,定理1.8证明了
是一个边数最多的
-禁止图。
定理1.9. 对于
,则
注意到当
时,根据定理1.7和1.9可以推出
。显然,
是一个
-禁止图,定理1.9证明了
是一个边数最多的
-禁止图。
下面让我们回顾证明中需要用到的符号和引理。对于任意的
,用
表示由顶点集合X和边集合
构成的子图。令
,用
表示G中与X中顶点相邻的所有顶点的集合。我们将
简写为
。图G顶点x的度
表示
的大小。在不会引起混淆的情况下,我们通常将省略下标。我们用
表示图G中顶点度的最小值。图G的周长
定义为G中最长圈的长度。
Dirac [17] 在1952年证明了下面的引理。
引理1.1. 若G是一个n个点的二连通图,则
本文结构安排如下:在第二节中,我们证明了定理1.8。在第三节中,我们证明了定理1.9。
2. 定理1.8的证明
本节中,我们对
-禁止图
的最大边数问题进行研究。
定理1.8的证明令G为一个n个顶点的
-禁止图。
情况1:
。
我们对n进行归纳。当
时,由于
,根据定理1.7可得
现假设定理1.8在
时结论都成立,下面证明结论对n成立。
若G不是连通的,不妨设
是G的含有
个顶点的连通分支,则由归纳假设可知
若G不是二连通的,不妨设
是G的含有
个顶点的二连通分支,同样由归纳假设可知
若G是二连通的,当
时,若存在一个点v,使得
,则
若
,根据引理1.1可知
,即图G一定包含一个长度大于等于
的圈,矛盾。
情况2:
。
我们对n进行归纳。当
时,由于
,根据定理1.7可得
现假设定理1.8在
时结论都成立,下面证明结论对n成立。
若G不连通或一连通,则类似情况1.中的证明,仍可得
若G是二连通的,当
时,若存在一个点v,使得
,则
若
,根据引理1.1可知
,即图G一定包含一个长度大于等于2k
的圈,矛盾。
3. 定理1.9的证明
类似于定理1.8的证明,我们利用数学归纳法来对
为奇数时的
-禁止图
的边数的上界进行估计。
定理1.9的证明 令G为一个n个顶点的
-禁止图。当
为奇数,令
。
我们对n进行归纳。当
时,由于
,根据定理1.7可得
现假设定理1.9在
时结论都成立,下面证明结论对n成立。
若G不是连通的,不妨设
是G的含有
个顶点的连通分支,则由归纳假设可知
若G不是二连通的,不妨设
是G的含有
个顶点的二连通分支,同样由归纳假设可知
若G是二连通的,当
时,若存在一个点v,使得
,则
若
,根据引理1.1可知
,则图G一定包含一条长度为
的路,矛盾。
4. 结论
本文主要利用数学归纳法研究具有n个顶点的
-禁止图,文中给出了n个顶点的
-禁止图的边数的上界。此外,文中还对任意n个顶点的
-禁止图,当
为奇数时,给出了
-禁止图的边数的一个上界。
NOTES
*通讯作者。