Domination and Colouring Games in Graphs

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

The principal objective and long term goal of my research program is the advancement of combinatorics knowledge with a focus on studying the connections between proper colourings and independence and domination in graphs. For the short term, I strive to find a balance between working on new, innovative problems and classical, well studied questions. Many of the recent innovations in this direction are stated in the form of dynamic and discrete-time graph processes and games. An additional objective of this program is the training of highly qualified personnel. It is important that more young Canadians have the skills and knowledge for advanced mathematics. Training is an integral part of my research program, primarily by attracting top young researchers to mathematical research projects (undergraduate and Master's students). The concept of colouring captures the interest of many 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 has been central in the concept of Graph Theory. Part of this research program looks at variations of map colourings in a quest to gain a stronger theoretical knowledge in the field. Industries, such as cellular networks, apply the theory of colouring to minimize the cost of purchasing channels. Channel assignment problems, with varying levels of network interferences, are not currently well understood and will be studied in this investigation. The theory of colouring is intimately related to independence and domination. Finding new connections between these topics is of primary interest in this investigation. The extremes of known relationships between colouring, independence and domination will be explored. To help develop new techniques, certain connections will be refined by restricting our attention to a smaller, subclass of graphs. Dynamic and discrete time processes can be used to model many fascinating games that have real-life applications. One can think of "eternal domination" as deploying mobile resource centers during a disaster or emergency situation. These mobile units have to be situated and moved in such a way that they adequately respond to any sequence of emergencies. It is often critical to maximize the use of resources in such a situation. The "firefighter problem" models the spread and containment of fire over a map. Our main goal is to determine the minimum resources needed to protect a certain proportion of the map. Another goal is to minimize the number of nodes a fire burns before being contained. This goal can be complicated by political needs which produce additional constraints. The problem can also be thought of as a virus spreading through a network, or a rumour through a population. Somewhat surprisingly, bounds on the number of resource centers in eternal domination are closely related to colourings and independence. Answers to questions poised in the firefighter problem are often found using the same techniques as the map colouring and channel assignment problem. The research program builds on the established success in these areas to make strong contributions to the exploration and advancement of Combinatorics. An additional impact of this proposal is the anticipated involvement of HQP in these projects. Opportunities for student inclusion in the above problems are included in the HQP Training Plan. Successful completion of any of the projects will provide a solution of interest to the combinatorics community and will further our understanding of colouring, independence and domination and the connections between these concepts. It is hoped that methods developed as part of this research program will be useful tools for future scholars.