Some Problems in Graph Theory

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

A graph is a set of vertices together with a set of edges. 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 this proposal, we consider some graph theoretic problems. In particular, we focus on three areas: graph searching (Cops and Robber), graph colouring/labelling as above, and graph packings. 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. One application of the proposed research in graph searching is network security. Computer networks are often targeted by viruses (and worms, Trojan horses, etc.). Although one layer of security is provided by firewalls and antivirus software, all that is needed for the security of the entire network to be jeopardized is for one individual computer to be vulnerable, due to out of date antivirus software, for example. 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. 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. With regard to my work in graph packings, many problems of both practical and theoretical interest involve packing objects into a structure. For example, one might want to store as many radioactive containers as possible in a building without, say, any k containers being too near each other. This situation can be modelled via k-limited packings. This proposal considers 2-limited packings of complete grid graphs. Such graphs naturally arise in applications involving city planning and electrical circuit layouts.