(修正)Szeged指标的极值问题的研究

Distance is one of the most basic concepts of graph-theoretic subjects. There are many elegant and powerful results on average distance in graph theory. Wiener index is an equivalent concept with average distance and is also the oldest topological index, Szeged index and revised Szeged index are extentions of Wiener index, and two important topological indices. Besides its theoretical interest in combinatorial mathematics, revised Szeged index also finds practical applications in many problems of chemistry.. This project will study the low bounds of the revised Szeged index and characterize the extremal graphs of those bounds. By combining the classical methods in graph theory and probability method, we will study the relations between the (revised) Szeged index and other invariants of graph.Using the construction properties of connected graphs and extremal graph theory,we will study the difference (ratio) between the revised Szeged index and the Wiener index. Since the (revised) Szeged index has been used to explain various chemical and physical properties of molecules and to correlate the structure of molecules to their biological activity, the study of the revised Szeged index attracts interesting of many researchers.

距离是图论学科中最基本的概念之一，关于平均距离，已经有许多优美、强大的结果。Wiener指标是平均距离的一个等价概念，也是最早被研究的拓扑指标，Szeged指标和修正Szeged指标是Wiener指标的一种自然、漂亮的推广，也是非常重要的两个拓扑指标。（修正）Szeged指标不仅在组合数学中重要的理论意义，而且在化学图论等领域有着重要的实际应用背景。. 本项目将研究修正Szeged指标的下界和刻画达到下界的极图；将经典图论的方法和概率方法相结合，研究（修正）Szeged指标与图的其它不变量之间的关系；利用连通图的结构性质以及极图理论研究（修正）Szeged指标与Wiener指标之间的关系。由于（修正）Szeged指标可以用来解释分子的各种物理化学性质以及与分子结构相关联的生物活性，所以（修正）Szeged指标起了众多研究者的兴趣。

距离是图论学科中最基本的概念之一，关于平均距离，已经有许多优美、强大的结果。Wiener指标是平均距离的一个等价概念，也是最早被研究的拓扑指标，Szeged指标和修正Szeged指标是Wiener指标的一种自然、漂亮的推广，也是非常重要的两个拓扑指标。（修正）Szeged指标不仅在组合数学中重要的理论意义，而且在化学图论等领域有着重要的实际应用背景。..本项目主要研究了修正Szeged指标的界值问题并刻画达到界值的极值图。首先，对于双圈图，我们计算了边修正Szeged指标的上界，此上界优于一般图的上界，同时刻画了所有达到上界的极值图；其次，我们给出了双圈图（三圈图）的修正Szeged指标的下界，同时刻画了所有达到下界的极值图；再次，我们刻画了稀疏图和稠密图的彩虹点联通的性质；最后，我们解决了李莎莎在她博士论文中提出的关于广义连通度复杂性的猜想,同时，对于广义边连通度的问题，我们给出一个多项式时间算法。