距离参数及若干相关的极值问题

Extremal graph theory is one of the most important branches of graph theory. Extremal problems on graphs and graphic parameters are main research contents of extremal graph theory. The investigation of extremal problems can make us know how global properties of a graph can determine or be determined by its substructures. The existence problem of subgraphs is both a classical and an important problem in graph theory. There is an important linkage between the extremal problem and existence problem of subgraphs. All research contents of this project are as follows: three kinds of extremal problems on the total distance of trees under three-parameter constraint, the existence problems of some subgraphs under distance conditions, and two conjectures concerning the relationship between graph radius and Randic index. One innovation point of our project is the investigation of extremal problems on total distance of trees under three-parameter constraint, which is an entirely new research content, and can be deemed as the innovation of research contents. Another innovation point of our project is the characterization of existence of some subgraphs using several distance parameters, which can be deemed as the innovation of research method. We aim to make important progress and achieve creative results on the study of extremal problems on total distance, to make creative results on the study of existence problems of subgraphs, and to extend previous relevant results by other scholars about two conjectures concerning the relationship between graph radius and Randic index.

极值图论是图论最重要的分支之一。图及图参数的极值问题是极值图论的主要研究内容。通过对极值问题的研究，可以使我们明确知道图的全局性质如何决定或者决定于图的子结构。子图存在性问题是图论里面经典的、重要的问题。极值问题与子图存在性问题有着重要的联系。本项目研究内容：三种三参数限制条件下树的全距离的极值问题；距离条件下一些子图的存在性问题；图半径与Randic 指标关系的两个猜想。三参数限制条件下树的全距离的极值问题是全新的研究内容，属于研究内容的创新；运用几个新的距离参数刻画某些子图的存在性，是子图存在性问题研究方法的一种创新。本项目拟在全距离的极值问题的研究上取得重要进展和创新性成果；在子图存在性问题的研究上取得创新性成果；在图半径与Randic 指标关系的两个猜想的研究上扩展前期相关学者的研究结果。

本项目围绕J. Plesník 提出的关于全距离极值的公开问题及 Delaviña 和B. Waller 提出的全距离极值问题的猜想，距离条件下特殊子图存在性问题及图的距离参数之间的关系展开研究。 主要研究若干距离参数相关的极值问题，距离条件下一些特殊子图的存在性问题，图的若干距离参数之间的关系。.研究内容：研究了包含全距离，Wiener极指标，边缘距离和，电阻Harary指标在内的若干距离参数的极值问题；研究了离心距离和与度距离之间的关系，研究了Harary指标，连通离心度指标，Wiener极指标及平均距离之间的关系；研究了特殊子图存在性问题，运用距离参数Wiener指标和Harary指标解决了最小度给定的连通图的可迹性及哈密顿性问题；在2-连通赋权图中，给出了三个赋权的度条件，使得在这些条件下，原2-连通赋权图包含经过一个给定端点或者两个给定端点的重路或者哈密顿路。.重要成果：部分解决了Delaviña 和 Waller于2008年提出的关于全距离极值问题的一个猜想，证明了该猜想在2-连通图时的正确性；运用距离参数Wiener指标和Harary指标完整解决了最小度给定的连通图的可迹性及哈密顿性问题；确定了图的离心距离和与度距离之间的关系，边缘距离和与全距离的关系及其他一些距离参数之间的关系。 .科学意义：图及图参数的极值问题是极值图论的主要研究内容。通过对极值问题的研究，可以使我们明确知道图的全局性质如何决定或者决定于图的子结构。本项目所研究的距离参数相关的极值问题，既是深化极值问题研究的需要，又是寻求解决极值问题的新方法的需要。而且，极值问题研究过程中遇到的极值结构也能深化我们对某些具体问题的理解。通过研究一些具体的距离参数的极值问题来探索解决这类问题的一般方法。对于极值问题研究过程中碰到的特殊子图进行性质分析，使我们对图的结构和性质的关系之间有一个更好的把握。研究距离条件下子图存在性问题能够使我们通过分析特殊子图的结构，及距离参数的性质，将两者之间建立一个紧密联系。有时候在解决极值问题的过程中需要借助于图论以外的其他组合数学分支以及其他数学分支中的方法。所以，对极值问题的研究可以在一定程度上推动整个组合数学及其他数学分支的发展。