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

图及其结构：图的局部属性和全局属性之间的相互作用

• 批准号: RGPIN-2016-05237
• 负责人: Oellermann, Ortrud
• 金额: $ 1.6万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=615576
• 关键词: Graphs; their; structure; interplay; between

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.

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