Some Further Problems in Graph Theory

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

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.