COLOURING, DOMINATION AND DISCRETE DYNAMIC GRAPH PROCESSES

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

• 批准号: RGPIN-2020-07156
• 负责人: Finbow, Stephen
• 金额: $ 1.75万
• 依托单位: St. Francis Xavier University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=718719
• 关键词: 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提供高质量的研究培训和发展，以支持下一代未来的成功。