COLOURING, DOMINATION AND DISCRETE DYNAMIC GRAPH PROCESSES

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

The principle objective and long-term vision of my research program is the exploration and advancement of optimal resource allocation in networks. Short-term objectives focusing in three areas, colouring and partitions, independence and domination and dynamic process in graphs, support the long-term aim of this program. Included in my program is the training of highly qualified personnel (HQP) to build a diversified and competitive research base. It is essential to provide the training to develop a strong mathematical culture in Canada so students have the skills and knowledge to succeed. The concept of colouring captures people's interest via simply stated, but difficult questions. For example, can a map be coloured with four colours so that countries sharing a border receive different colours? This question is central in the concept of Graph Theory. A focus of this research program examines variations of map colourings, such as viewing them as a partition of the vertex set of a graph, to advance theoretical knowledge in the field. Industries, such as cellular networks, apply the theory of colouring to minimize the cost of purchasing channels. The theory of colouring is intimately related to independence and domination. Finding new connections between these topics is a long-term objective. The extremes of known relationships between colouring, independence and domination will be explored. To aid in the development of new techniques, relevant connections will be refined by restricting our attention to a smaller, subclass of graphs. Discrete dynamic processes are used to model many fascinating games that have real-life applications. One can view dynamic domination as deploying mobile resource centers during a disaster or emergency situation. These mobile units must be situated and moved in such a way that they sufficiently respond to any sequence of emergencies. It is often critical to optimize the use of resources. The "firefighter problem" models the spread and containment of fire over a map. Our aim is to determine the minimum number of resources required to protect a certain proportion of the map. A further objective is to minimize the number of nodes a fire burns before being contained. The model can also be applied to a virus spreading through a network, or a rumour/fake news through social media. Somewhat surprisingly, bounds on the number of resource centers in dynamic domination are closely related to colourings and independence. Answers to questions poised in the firefighter problem are often found utilizing the same techniques as the map colouring and channel assignment problem. This research program builds on the established success in these areas to deliver meaningful contributions to the exploration and advancement of optimal resource allocation. An additional important impact of the program is the quality research training and development provided for HQP to support the future success of the next generation.