Graphs and their structure: the interplay between local and global properties of graphs

对于各种情况，如社会、协作、通信和运输网络，以及化学结构和动态过程，图是简单和容易理解的模型。互联网的发展以及由此产生的大型通信网络深刻地影响了图论的发展。特别令人感兴趣的是网络的全局结构与其局部属性之间的关系。更深入地了解网络的全局和局部属性之间的相互作用在算法过程中是有用的。一方面，我们建议在网络的全局和局部属性/结构之间建立新的联系；另一方面，我们建议利用某些网络类型的全局和局部结构之间的现有联系来寻找解决网络难题的有效方案。我们拟议的工作有四个主要主题，概述如下。 我们建议研究网络的某些拓扑指数--“度量”与其结构之间的联系。其中一个被广泛研究的指数是维纳指数，因为它与物质的化学性质有关而被研究。它是对网络中节点对之间或分子结构中原子之间的平均距离的测量。与图相关的是各种凸性，通常用称为区间的局部结构来定义。例如，一对节点之间的最短路径间隔由位于这对节点之间最短路径上的所有节点组成。如果一个结点集包含所有结点对之间的间隔，则它是凸的。我们建议探索网络结构与此类凸集的数目和平均大小之间的关系。 我们还建议研究如何根据关于网络结构的部分信息来重建网络。例如，有人可能会问，Facebook图是否可以从其用户的朋友列表中唯一地重建。数字图像处理导致了根据当地情况定义的网络的数字凸性。我们计划从网络的数字凸性来研究网络的重构问题。 该提议的另一个方面涉及可以从其节点的邻域信息推断出的网络的全局循环结构。这一领域已经完成的一些工作表明，如果一个网络中节点的邻域具有丰富的循环结构，那么全球结构也是如此。 最后，我们建议研究度量维度及其变种。公制维度有许多应用，包括网络安全、网络空间中机器人的导航、化学过程和策划者游戏的解决方案。计算网络的度量维度是一个困难的问题。之前已经研究了许多变体。对于结构良好的网络，我们提出了对这些不变量的比较研究，并且已经取得了一些结果。

Graphs serve as simple and easily understood models for various situations such as social, collaboration, communication and transportation networks as well as for chemical structures and dynamical processes. The development of graph theory has been profoundly influenced by the evolution of the internet and resulting large communication networks. Of particular interest are relationships between the global structure of the network and its local properties. A deeper understanding of the interplay between global and local properties of a network is useful in algorithmic processes. On the one hand we propose to establish new connections between global and local properties/structures of networks and on the other hand we propose to use existing connections between global and local structures of certain network types to find efficient solutions for difficult network problems. Our proposed work has four main themes as outlined below. We propose to study connections between certain topological indices, “measures”, of a network and its structure. One such widely studied index is the Wiener index, examined because of its connections with chemical properties of substances. It is a measure of the average distance between pairs of nodes in a network or between atoms in a molecular structure. Associated with a graph are various convexities usually defined in terms of local structures called intervals. For example, the shortest path interval between a pair of nodes, consists of all nodes that lie on a shortest path between this pair. A set of nodes is convex if it contains the interval between all pairs of nodes. We propose to explore connections between the structure of a network and the number and average size of such convex sets. We also propose to examine how to reconstruct networks from partial information about the structure of the network. For example, one may ask if the Facebook graph can be uniquely reconstructed from the friends lists of its users. Digital image processing gave rise to the digital convexity of a network defined in terms of local conditions. We plan to study the reconstruction problem of a network from its digital convexity. Another aspect of this proposal deals with global cycle structures of networks that can be deduced from neighbourhood information of its nodes. Some work, already completed in this area, suggests that if the neighbourhoods of nodes in a network have a rich cycle structure, then so does the global structure. Finally we propose to study the metric dimension and its variants. The metric dimension has many applications including network security, navigation of robots in a network space, chemical processes, and solutions of the mastermind game. It is difficult to compute the metric dimension of a network. Many variations have been studied previously. We propose a comparative study of these invariants for well-structured networks for which we have already obtained some results.