Some Further Problems in Graph Theory

图论中的一些进一步问题

• 批准号: RGPIN-2020-06528
• 负责人: Clarke, Nancy
• 金额: $ 1.31万
• 依托单位: Acadia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=741295
• 关键词: Some; Further; Problems; Graph; Theory

In this proposal, we consider some graph theoretic problems. In particular, we focus on three areas: graph searching (Cops and Robber), graph colouring/labelling, and graph reconfiguration which intersects with the other two areas. The research program described here has several themes. For instance, we will often be interested in studying the structural properties of the graphs under consideration. My primary objective in undertaking this research is to advance knowledge in the field of graph theory. In addition to keeping Canada at the forefront of such mathematical research, there are significant practical applications of the proposed research program. Graphs make great models. For instance, we can represent the regions of a map by vertices, with two vertices adjacent, i.e. joined by an edge, whenever the corresponding regions share a non--trivial border. When printing maps, it is desirable to minimize the number of colours needed so that regions which share a border receive different colours. In terms of the corresponding graph, we would like to minimize the number of colours, or simply labels, needed to colour the vertices in such a way that adjacent vertices receive different colours. This is the well--studied graph colouring problem. In addition to the many applications of graph colouring/labelling in scheduling and resource allocation, one application of my work in Skolem labelling is to model the configuration of communications networks with a central hub which directs information to different nodes of the network. One application of the proposed research in graph searching is network security. Computer networks are often targeted by malware. Although one layer of security is provided by firewalls & antivirus software, all that is needed for the security of the entire network to be jeopardized is for one computer to be vulnerable. My research in graph searching looks at addressing this weakness in network security by developing efficient algorithms that are designed to locate these viruses so that they can be quarantined before infecting the network. Other applications include criminal apprehension, building security, the tracking of users in cellular networks, and solving telecommunications problems related to routing. With regard to my work in reconfiguration, many problems of both practical and theoretical interest involve appropriate transitions from one configuration to another. For example, if a subset of routers in a network are monitoring packet flow, the need for maintenance will regularly make it necessary to transition from one set of routers to another. Of course, monitoring must be uninterrupted during the changeover. This problem can be modelled via the reconfiguration of vertex covers in a graph. As above, one aspect of this proposal is reconfiguration of cops/guards in a network. The proposed research program will provide training opportunities at the undergraduate, graduate, and postdoctoral levels.

在这个建议中，我们考虑一些图论问题。特别是，我们专注于三个领域：图搜索（警察和强盗），图着色/标签，和图重新配置与其他两个领域相交。这里描述的研究计划有几个主题。例如，我们经常对研究所考虑的图的结构性质感兴趣。我从事这项研究的主要目标是推进图论领域的知识。除了保持加拿大在这样的数学研究的前沿，还有重大的实际应用的拟议研究计划。图表是很好的模型。例如，我们可以用顶点来表示地图的区域，只要相应的区域共享一个非平凡的边界，两个顶点相邻，即由一条边连接。当打印地图时，期望最小化所需颜色的数量，使得共享边界的区域接收不同的颜色。在相应的图中，我们希望最小化颜色的数量，或者简单地说，以相邻顶点接收不同颜色的方式为顶点着色所需的标签。这是很好的研究图着色问题。除了许多应用程序的图着色/标签在调度和资源分配，一个应用程序，我的工作在Skolem标签是模拟配置的通信网络与一个中央枢纽，将信息发送到不同的节点的网络。 所提出的研究在图搜索中的一个应用是网络安全。计算机网络经常成为恶意软件的目标。虽然防火墙和防病毒软件提供了一层安全性，但整个网络的安全性受到危害所需的只是一台计算机容易受到攻击。我在图搜索方面的研究着眼于通过开发有效的算法来解决网络安全中的这一弱点，这些算法旨在定位这些病毒，以便在感染网络之前对其进行隔离。其他应用包括刑事逮捕，建筑安全，跟踪蜂窝网络中的用户，以及解决与路由相关的电信问题。关于我在重新配置方面的工作，许多实际和理论上都感兴趣的问题涉及从一种配置到另一种配置的适当转换。例如，如果网络中的一个路由器子集正在监视数据包流，则维护的需要将定期从一组路由器转换到另一组路由器。当然，在转换过程中，监控必须不间断。这个问题可以通过重新配置图中的顶点覆盖来建模。如上所述，该提议的一个方面是网络中警察/警卫的重新配置。拟议的研究计划将提供本科生，研究生和博士后水平的培训机会。