Some Further Problems in Graph Theory

点击翻译按钮获取中文摘要

In this proposal, we consider some graph theoretic problems. In particular, we focus on three areas: graph searching (Cops and Robber), graph colouring/labelling, and graph reconfiguration which intersects with the other two areas. The research program described here has several themes. For instance, we will often be interested in studying the structural properties of the graphs under consideration. My primary objective in undertaking this research is to advance knowledge in the field of graph theory. In addition to keeping Canada at the forefront of such mathematical research, there are significant practical applications of the proposed research program. Graphs make great models. For instance, we can represent the regions of a map by vertices, with two vertices adjacent, i.e. joined by an edge, whenever the corresponding regions share a non--trivial border. When printing maps, it is desirable to minimize the number of colours needed so that regions which share a border receive different colours. In terms of the corresponding graph, we would like to minimize the number of colours, or simply labels, needed to colour the vertices in such a way that adjacent vertices receive different colours. This is the well--studied graph colouring problem. In addition to the many applications of graph colouring/labelling in scheduling and resource allocation, one application of my work in Skolem labelling is to model the configuration of communications networks with a central hub which directs information to different nodes of the network. One application of the proposed research in graph searching is network security. Computer networks are often targeted by malware. Although one layer of security is provided by firewalls & antivirus software, all that is needed for the security of the entire network to be jeopardized is for one computer to be vulnerable. My research in graph searching looks at addressing this weakness in network security by developing efficient algorithms that are designed to locate these viruses so that they can be quarantined before infecting the network. Other applications include criminal apprehension, building security, the tracking of users in cellular networks, and solving telecommunications problems related to routing. With regard to my work in reconfiguration, many problems of both practical and theoretical interest involve appropriate transitions from one configuration to another. For example, if a subset of routers in a network are monitoring packet flow, the need for maintenance will regularly make it necessary to transition from one set of routers to another. Of course, monitoring must be uninterrupted during the changeover. This problem can be modelled via the reconfiguration of vertex covers in a graph. As above, one aspect of this proposal is reconfiguration of cops/guards in a network. The proposed research program will provide training opportunities at the undergraduate, graduate, and postdoctoral levels.