图的一些极值问题研究

摘要

1978年，Bollobás在他的著作《极值图论》中[3]指出，图的极值理论主要研究的是，图中的某些变量，如阶数，大小，连通度，最小度，最大度，色数，直径足够大时，图中一定出现某些结构.本文主要研究了两类极值问题:x-有界问题和3-一致超图的Turán数问题.
　　令x(G)，R(l，j)分别表示图的色数和Ramsey数.给定图G和H，若V(H)(∈)V(G)，且E（H）={uv|{u，v}∈V（H）且uv∈E(G)}，则称H为G的一个诱导子图.Gyárfás和Sumner分别独立地提出了以下猜想:对于任意的树T，存在一个函数厅(x)使得每一个色数大于fT(ω(G))的图均包含T作为诱导子图，其中ω(G)表示图G的团数.我们称fT(x)是一个界定函数.
　　关于x-有界猜想，我们做的具体工作如下:
　　1.Gyárfás，Szemerédi和Tuza证明了若一个图G不含三角形和长为4的圈，则G含有任一个x(G)个顶点的树作为诱导子图.我们推广了Gyárfás等人的这个结果，证明了:若图G的任一个顶点至多含在k个三角形和l个长为4的圈中，且x(G)≥t+2k+2l，则G包含任一个t个点的树作为诱导子图.
　　2.Gyárfás，Szemerédi和Tuza证明了若G不含三角形，且x(G)≥m+n，则G一定包含一个特殊的树（m，n）-单杠星图作为诱导子图.我们推广了他们的结果，证明了:如果图G中的每一个顶点至多包含在k个三角形中，并且不能够诱导出T，那么，x(G)＜m（k+1）+n，其中T为(m，n)-单杠星图.
　　3.Gyárfás给出了路Pn与星图Sn的界定函数，结合这两个结果与证明方法，我们找到了(m，n)-单杠星图的两个界定函数，证明了:令m和n表示大于2的整数，T表示一个(m，n)-单杠星图.那么，Forb(T)图是x-有界的，并且f(x)=mx-1R(3n-2，x)是一个界定函数.更进一步地，如果g(x)=(m-1)x-1(2n)xR（3n-2，x），并且x(G)≥g(ω(G))，那么，对于每一个度至少为R(2n-1，ω(G))的顶点v，G能够诱导出一个(m，n)-单杠星图，并且中心点与v的距离至多为2.
　　4.Scott从拓扑的角度证明了，对于任意半径为r的树T和正整数k，每一个色数充分大的图G，其中ω(G)≤k，均能够诱导出T的一个剖分，使得每条边被至多剖分成O（14r-1(r-1）!）次.我们通过对诱导子树的结构和证明过程中的划分进行了改进，证明了:对于任意半径为r的树T和正整数k，每一个色数充分大的图G，其中ω(G)≤k，均能够诱导出T的一个剖分，使得每条边被至多剖分成O(6r-2)次.
　　令ex3（n，kG）表示恰含n个顶点的3-一致超图中不包含kG作为子图的最多的边数，其中，kG表示3-一致超图G的k个不交并.并且，我们称ex3(n，kG)为kG的Turán数.2011年，Gorgol给出了简单连通图不交并的Turán数，并且给出了当k=2与k=3时，kP2的Turán数，这个值与定理中的下界是相同的.在本文中，我们将这些结果推广到3-一致超图中，得到了3-一致超图的不交并的Turán数的上界与下界，并且给出当图中的顶点数很大时，能够达到下界的极图:kP2+.
　　关于3-一致超图不交并的Turán数，我们得到的具体结果如下:
　　5.令G表示任意一个恰含m个顶点的连通3-图，k表示任意一个正整数，n是一个满足n≥mk的整数.那么，ex3(n，kG)≥max{c1，c2}，其中，c1=ex3(n-km+1，G）+(km-13);c2=ex3（n-k+1，G）+f（n，k），f(n，k)=（k-13）+(k-1)（n-k+12）+(n-k+1)（k-12）.
　　6.令G表示任意一个恰含m个顶点的连通的3-图，k表示任意一个整数.那么，ex3（n,kG）≤ex3（n-（k-1）m，G）+f（n，（k-1）m+1），其中f(n，x)=(x-13)+(x-1)(n-x+12)+(n-x+1)(x-12).
　　同时，我们证明了，当k为2的N次幂时，可以得到一个较小的上界.
　　7.令G表示任意一个恰含m个顶点的连通3-图，k为2的N次幂（其中N为正整数）.那么，ex3(n，kG)≤ex3(n-(k-1)m，G）+log2k-1∑i=0g(n-km+1/2(i)km，k/2(i)，m），其中g（n，k，m）=(1/2km3)+（1/2km2）（n-1/2km）+1/2km（n-1/2km2）.
　　我们称图G=(V,E)的一个r-扩展图G+的顶点集为G的顶点集，边集为{e∪Se:e∈G}，满足|Se|=r-2，Se∩V(G)=Φ，Se∩Se'=Φ，其中e≠e'.令P2表示恰含3个顶点的路.本文中，kP2+表示P2的3-扩展图的k个不交并.我们证明了，当n充分大时，kP2+的Turán数.
　　8.当n＞43k-21/2时，有ex3(n，kP2+)={n-k+1+f(n，k)n≡0(mod4)n-k+f(n，k)n≡1(mod4)n-k-1+f(n，k)n-2,3(mod4)其中f(n，k)=(k-13)+（k-12）(n-k+1)+(k-1)(n-k+12）.

目录

声明

摘要

第1章 前言

1．1 基本的符号

1．2 研究背景及相关结果

1．3 x-有界猜想

1．4 3-一致超图的Turán数

第2章 关于x-有界猜想的一些结果

2．1 树T在特殊图类上的界定函数

2．2 (m，n)-单杠星图在特殊图类上的界定函数

2．3 (m，n)-单杠星图的两个界定函数

2．4 关于树T的剖分次数的改进

第3章 3-一致超图的Turán数

3．1 3-一致超图的Turán数的下界

3．2 3-一致超图的Turán数的上界

3．3 kP+2的Turán数

参考文献

攻读博士学位期间所发表及已完成的论文

致谢