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.