Domination and Colouring Games in Graphs

图表中的统治和着色游戏

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

我的研究计划的主要目标和长期目标是组合数学知识的进步，重点是研究正确的着色和图中的独立性和控制之间的联系。在短期内，我努力在研究新的、创新的问题和经典的、研究得很好的问题之间找到平衡。在这个方向上的许多最新的创新是以动态和离散时间图过程和游戏的形式提出的。该计划的另一个目标是培养高素质的人才。重要的是，更多的加拿大年轻人拥有高等数学的技能和知识。培训是我的研究计划的一个组成部分，主要是通过吸引顶尖的年轻研究人员到数学研究项目（本科生和硕士生）。着色的概念通过简单陈述，但困难的问题抓住了许多人的兴趣。例如，地图是否可以用四种颜色着色，以便共享边界的国家使用不同的颜色？这个问题一直是图论概念的核心。这项研究计划的一部分着眼于地图着色的变化，以获得该领域更强的理论知识。诸如蜂窝网络之类的行业应用着色理论来最小化购买渠道的成本。信道分配问题，不同程度的网络干扰，目前还没有很好地理解，将在本次调查中进行研究。色彩理论与独立性和支配性密切相关。寻找这些主题之间的新联系是本研究的主要兴趣。色彩，独立和统治之间的已知关系的极端将被探讨。为了帮助开发新的技术，某些连接将通过限制我们的注意力到一个较小的，图的子类来细化。动态和离散时间过程可以用来模拟许多具有现实应用的有趣游戏。人们可以把“永恒的统治”看作是在灾难或紧急情况下部署移动的资源中心。这些移动的单位必须以适当的方式安置和移动，以便对任何一系列紧急情况作出适当的反应。在这种情况下，最大限度地利用资源往往至关重要。“消防员问题”在地图上模拟火灾的蔓延和遏制。我们的主要目标是确定保护一定比例的地图所需的最低资源。另一个目标是最小化火灾在被控制之前燃烧的节点数量。这一目标可能因政治需要而变得复杂，从而产生额外的限制。这个问题也可以被认为是通过网络传播的病毒，或者是通过人群传播的谣言。有些令人惊讶的是，在永恒的统治中，资源中心的数量界限与颜色和独立性密切相关。消防员问题的答案通常使用与地图着色和通道分配问题相同的技术来找到。该研究计划建立在这些领域的既定成功的基础上，为组合数学的探索和发展做出了巨大贡献。本提案的另一个影响是预期HQP将参与这些项目。学生参与上述问题的机会包含在HQP培训计划中。任何项目的成功完成都将为组合数学界提供一个感兴趣的解决方案，并将进一步加深我们对着色，独立性和支配以及这些概念之间联系的理解。希望作为本研究计划的一部分开发的方法将是未来学者的有用工具。