Domination and Colouring Games in Graphs

图表中的统治和着色游戏

• 批准号: RGPIN-2014-06571
• 负责人: Finbow, Stephen
• 金额: $ 0.8万
• 依托单位: St. Francis Xavier University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=589094
• 关键词: Domination; Colouring; Games; 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.

我的研究计划的主要目标和长期目标是提高组合学知识，重点研究图中适当着色与独立性和支配性之间的联系。在短期内，我努力在研究新的、创新的问题和经典的、研究得很好的问题之间找到平衡。最近在这方面的许多创新都是以动态和离散时间图形过程和游戏的形式来陈述的。这个项目的另一个目标是培养高素质的人才。让更多的加拿大年轻人掌握高等数学的技能和知识是很重要的。培训是我的研究计划的一个组成部分，主要是通过吸引顶尖的年轻研究人员参与数学研究项目（本科生和硕士生）。