图的平均距离及相关问题研究

本项目研究图的平均距离及与之相关问题，主要包括图的平均距离与其他参数关系、算法问题以及Hosoya多项式、距离嵌入问题。 首先，探讨连通图中平均距离与图中诸如连通控制数、（连通）枢纽（hub）数、图的阶、半径、直径等参数之间关系，并决定极值图； 第二，分别探讨弦图的平均距离及构造最小平均距离支撑树和团树的线性算法；第三，研究Hosoya多项式，包括典型图上的计算，Hosoya多项式的单峰性和递推公式等数学性质；最后，为了更有效地计算距离，研究图的距离嵌入到超立方体图。图的平均距离是图紧凑性的一个自然度量，在通讯网路的设计和分析、化合物物理化学性质研究中扮演重要角色，是该领域一个持续关注方向； 一些挑战性问题相继被提出，许多基本问题亟待解决。通过本项目的研究提出有价值的研究方法，解决若干重要问题， 推动平均距离理论和应用的进一步发展。

The present project intends to study the average of the distances between vertices in the graph and the related problems, mainly including the relations between the average distance and other graph-parameters, algorithms on the average distance and, Hosoya polynomials, distance embedding. Firstly, we aim at investigating the relations between the average distance and other graph-parameters, such as the connected domination number, the (connected) hub number, radius, diameter or the order of the graph. Secondly, we explore linear algorithms for computing the average distance of a chordal graph and constructing its minimum average distance spanning trees and clique trees, respectively. Thirdly, we will investigate Hosoya polynomials of graphs, including computation on typical graphs and， mathematical properties , such as the unimodality, the recursive relationship, etc. Finally, for the sake of the efficient computation for distances of pairs of vertices, we will investigate the distance embeddings of graphs into hypercubes. The average distance of a graph is a natural measure of the compactness of the graph, plays an important role in the design of communication networks and their analysis, physico-chemical properties of compounds. This field has received unfailing attention from researchers. Some challenging problems have been put forward, and many fundamental ones need solving. This present project, therefore, will carry out systematic study on these issues to bring in valuable research methods, solve important problems and ultimately promote the average distance theories and their applications.