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

图作为简单易懂的模型，适用于各种情况，如社会、协作、通信和交通网络，以及化学结构和动态过程。图论的发展深受互联网的发展和由此产生的大型通信网络的影响。特别令人感兴趣的是网络的全局结构与其局部属性之间的关系。更深入地了解网络的全局和局部属性之间的相互作用在算法过程中是有用的。一方面，我们建议在网络的全局和局部属性/结构之间建立新的联系，另一方面，我们建议利用某些网络类型的全局和局部结构之间的现有联系，为困难的网络问题找到有效的解决方案。我们建议的工作有四个主题，概述如下。

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.