距离相关的一类Turan类极值问题的研究

The conjectures about Estrada index, the closed walk and the path with a given distance have been perfectly proved. As a natural generalization of these, the number of vertex-pairs with a given distance is a new Turan problem, and has a closely relationship between Wiener index and other chemical indicators; and further, also has a wide range of practical applications in chemical and network science and other fields..The project aims to study the number of vertex-pairs with a given distance, and aims to give the extremal values and character the extremal graphs. According to structural properties of the extremal graph, we will use graph transformation and analysis of a combination of methods to study some conjectures of Tyomkyn et al., and make order to solve them and portray the extremal graphs. Then by combining the classical methods in graph theory and probability method, we will study the problem of Bollobas et al., and further to give the relations and other invariants (such as maximal degree,diameter and girth so on) of graphs. Finally, we will study from the algorithm point of view, and use the concept of random algorithms to solve this extremal problem and character the extremal graph.

Estrada指数极值的猜想、给定长度值得闭路经数目极值的猜想和给定距离值的路的极值问题是极值图论与化学图论中的重要猜想，都已经得到了完美的解决。作为路径和路的自然延伸，距离相关的顶点对数目的极值问题是一类新的Turan类极值问题，与化学图论有着密切的联系，在化学与网络科学等领域有着广泛的实际应用。.本项目旨在研究距离相关的顶点对数目的极值与极图的刻画问题。围绕Tyomkyn等人的猜想，根据极图的结构性质，利用图操作与分析相结合的方法来研究距离相关的顶点对数目的极值问题，力争刻画相应的极图；在运用经典图论方法的基础上，试图引入概率方法来解决Bollobas等人关于给定参变量的树上顶点对数目的公开问题，更进一步研究与图的其它不变量（如：最大度、直径、围长等）之间的关系；从算法角度来考虑此问题，力争确定求解距离为给定值的顶点对数目极值问题的复杂性，并试图设计有效的算法。

Estrada指数极值的猜想、给定长度值得闭路经数目极值的猜想和给定距离值的路的极值问题是极值图论与化学图论中的重要猜想，都已经得到了完美的解决。作为路径和路的自然延伸，距离相关的顶点对数目的极值问题是一类新的Turan类极值问题，与化学图论有着密切的联系，在化学与网络科学等领域有着广泛的实际应用。本项目旨在研究距离相关的顶点对数目的极值与极图的刻画问题。项目组成员围绕Tyomkyn等人的猜想，根据极图的结构性质，利用图操作与分析相结合的方法来研究距离相关的顶点对数目的极值问题；项目负责人与人合作总结了近年来次方面问题的进展，写成综述论文一篇，已投稿；在运用经典图论方法的基础上，试图引入概率方法来解决Bollobas等人关于给定参变量的树上顶点对数目的公开问题，更进一步研究与图的其它不变量（如：最大度、直径、围长等）之间的关系，此部分项目组成功的解决了给定最大度条件下树上距离点对的极值问题，并刻画了相应的极图，论文发表在 Discrete appl. Math. 上。此外，在此基金的支持下，项目组还开展了对于图的控制集、染色等问题的研究，已取得相应的成果，被Discrete Math.等杂志接收发表。