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
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=661141
• 关键词: 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 图是否可以是唯一的。数字图像处理产生了根据局部条件定义的网络的数字凸性。我们计划从其数字凸性研究网络的重建问题。******另一个。该提案的一个方面涉及网络的全局循环结构，该结构可以从其节点的邻域信息中推断出来。该领域已经完成的一些工作表明，如果网络中节点的邻域具有丰富的循环结构，那么也具有丰富的循环结构。全局结构。*****最后我们建议研究度量维度及其变体。度量维度有很多应用，包括网络安全、网络空间中的机器人导航、化学过程和策划者游戏的解决方案。计算网络的度量维度是很困难的。 .我们之前已经研究了许多变化。我们提出了对结构良好的网络的这些不变量的比较研究，我们已经获得了一些结果。*****