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

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.

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

本课题主要研究是关于图中基于距离的参数之间关系，极值图刻画，参数计算和算法复杂性以及与之相关Hosoya多项式计算及性质等。在四年的资助期， 取得预期成果。 第一，建立参数之间大小关系，并刻画极值图及Hosoya多项式计算； 目前建立了平均距离（等价于理论化学中维纳指标）和连通枢纽数、连通控制数之间关系， 给出了一般图上平均距离关于这两个参数的紧上界，并刻画达到紧上界的极值图；把关于离心距离和（另一个重要拓扑指标）的一个猜想推进一步； 另外，分别给出了原冠状苯系统的完全强迫数和典型图类上全局强迫数的分析表达式、一般图上全局强迫数的紧上下界、几类典型图类上的Hosoya多项式的具体分析表达式、随机亚苯基链的Hosoya多项式期望值的分析表达式；第二，研究了关于一般序列单峰性的问题，证明了没有W_5-e作为导出子图的余可比图循环数为2， 部分解决了猜想；证明了典型凯莱图的可扩数。 第三，关于重要参数：控制数及变形参数的研究，并取得较好科研成果。主要有3个方面：1. 关于点控制参数，统一了经典控制参数和罗马控制参数并建立之间大小关系， 刻画极值树，证明了对于任意k， 罗马{k}-控制数问题分别在二部平面图和二部弦图上都是NP-完全的，刻画了2-控制数与罗马{2}-控制数相等的树，给出了有限非阿贝尔群上定义的半凯莱图中存在独立完美控制集的充要条件; 2. 边控制参数，证明了全边控制数问题在度小于4的二部图上是NP-困难的，通过边控制数给出树的全边控制数的上下紧界，证明了判断图的边控制数和半全边控制数相等、边控制数和全边控制数相等问题都是NP-困难的，分别刻画了满足边控制数和半全边控制数相等、边控制数和全边控制数相等的树，证明了树上2-彩虹边控制数和罗马{2}-边控制数相等，刻画2-彩虹边控制边和边控制数相等的树；3.控制临界图性质方面，证明了，对于任意整数t>2,如果3-连通的3-连通控制临界图G最小度大于t-2, 没有K_{1, t}作为导出子图，那么，G是双临界的；给出了k-全控制临界图G的一些性质，例如，diam(G)< 2k-2, 刻画了2-全控制临界图和3-全控制临界图， 刻画了不是双临界的3-连通、3-控制临界图。培养的毕业生7名，在读博士6名、硕士9名；完成24篇论文，发表11 篇，投稿8篇，正在准备5篇。举办会议1次，参加会议20余人次，邀请专家近40人。