COLOURING, DOMINATION AND DISCRETE DYNAMIC GRAPH PROCESSES

着色、控制和离散动态图形过程

• 批准号: RGPIN-2020-07156
• 负责人: Finbow, Stephen
• 金额: $ 1.75万
• 依托单位: St. Francis Xavier University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759276
• 关键词: COLOURING; DOMINATION; DISCRETE; DYNAMIC; GRAPH

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.

我的研究计划的主要目标和长期愿景是探索和推进网络中资源的最佳配置。短期目标集中在三个方面：着色和分区、独立和支配以及图形的动态过程，支持该计划的长期目标。我的计划包括培养高素质人才（HQP），以建立一个多元化和有竞争力的研究基地。在加拿大，为培养强大的数学文化提供培训是至关重要的，这样学生才能拥有成功所需的技能和知识。上色的概念通过简单明了但困难的问题抓住了人们的兴趣。例如，地图可以用四种颜色着色，以便共享边界的国家收到不同的颜色吗？这个问题是图论概念的核心。本研究计划的一个重点是检查地图着色的变化，例如将它们视为图的顶点集的分割，以推进该领域的理论知识。蜂窝网络等行业应用着色理论来最大限度地降低购买渠道的成本。色彩理论与独立和支配密切相关。寻找这些主题之间的新联系是一个长期目标。我们将探索色彩、独立和统治之间已知的极端关系。为了帮助新技术的发展，相关的联系将通过将我们的注意力限制在更小的图的子类来细化。离散动态过程用于模拟许多具有实际应用的有趣游戏。动态控制可以看作是在灾难或紧急情况下部署移动资源中心。这些流动单位的部署和移动必须使它们能够对任何一系列紧急情况作出充分反应。优化资源的使用通常是至关重要的。“消防员问题”在地图上模拟了火灾的蔓延和遏制。我们的目标是确定保护一定比例地图所需的最小资源数量。另一个目标是在火势被控制之前尽量减少节点的数量。该模型也适用于通过网络传播的病毒，或通过社交媒体传播的谣言/假新闻。令人惊讶的是，动态控制中资源中心的数量界限与颜色和独立性密切相关。在消防员问题中找到的问题的答案通常使用与地图着色和通道分配问题相同的技术。该研究项目建立在这些领域已取得的成功的基础上，为探索和推进最佳资源配置做出了有意义的贡献。该计划的另一个重要影响是为HQP提供的质量研究培训和发展，以支持下一代的未来成功。