度的幂和的Turan问题的研究

Supported by NSFC, the project has made many progress. We list as follows: One monograph (Springer), one translation and 11 papers are published and 2 papers are accepted for publication. The results of Krivelevich and Yuster are improved to be almost best by using the probabilistic method; One new method to compare the values of graph energy is established, from which some long-time unsolved open problems and conjectures are completely solved. In these years, the extremal problems on the sum of degree powers are very popular. Recently, Bollobas et al. investigated two new classes of Turan problems concerning the sum of degree powers of graphs. In this project, we will continue to consider the extremal problems on the sum of degree powers of graphs, especially the two new classes of Turan problems, and investigate a list of open problems proposed by Bollobas et al.. The main method we will use are the classical methods, the probabilistic method, graph transforms, analysis method, and so on. We are willing to obtain some new results and expand some systemic methods, which will be a new contribution to extramal graph theory.

青年科学基金项目取得了如下进展：出版专著（Springer出版社）1部、译著1部，（接受）发表科研论文13篇（其中11篇为SCI检索杂志），已发表11篇，接受发表2篇；用概率方法将Krivelevich等人的结果改进到几乎最好；建立了图能量（度的幂和的一种推广）比较的新方法，彻底解决了多个长期未决的公开问题和猜想。近年来，度的幂和的极值问题得到了包括Erdos、Bollobas和Katona等国际知名学者的关注和重视。最近Bollobas等人提出了与度的幂和相关的两类Turan问题并进行了深入研究。本项目将在青年科学基金项目的基础上，围绕Bollobas等人提出的一系列公开问题，继续研究度的幂和的极值问题，特别是两类Turan问题。我们将参考现有的研究方法，将经典图论方法与概率方法相结合，用图变换与分析结合的方法来开展研究，争取发展出一套系统的研究方法，这无疑将是对极图理论的新贡献。

本项目已按计划完成，达到预期目标. 主要取得了如下研究成果：（A）度的幂和方面，Bollobas等人研究了度的幂和的Turan类问题，并讨论了限制子图为偶圈的情形，奇圈的情形被认为是困难的，我们考虑限制子图为五圈的情形，对相应的极图进行了刻画；同时我们研究了森林的度的幂和的Turan问题，刻画了相应的极图。（B）图的极值问题方面，研究了随机有根树中模型的计数，得到了随机有根树中不同构模型数目的极限分布，这一结果解决了Gerard Kok博士毕业论文中的一个公开问题；研究了随机图的 k-连通度和 k-边连通度，给出了紧阈值函数以及关于最小度的 hitting time，我们的结果与 Bollobas 和 Thomassen 给出的经典（边）连通度的结果是一致的。（C）超图的极值问题方面，研究了非一致超图的拉格朗日与最大团的关系，给出了{1,r}-超图的Motzkin-Straus类型的结果；借助Frankl和Rodl等的研究方法，构造了5一致超图的一系列非jumping数。（D）另外，我们还考虑了基于距离的Turan类问题，以及圈和路的平面Turan类问题。（E）图的星边染色方面，研究了给出了Subcubic图的星边色数的上界，部分解决了Mohar等提出的关于Subcubic图的星边色数的猜想。（F）在图论与信息科学交叉方面，主要在网络熵和网络相似性方面展开研究。