Some Problems in Graph Theory

图论中的一些问题

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

A graph is a set of vertices together with a set of edges. 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 this proposal, we consider some graph theoretic problems. In particular, we focus on three areas: graph searching (Cops and Robber), graph colouring/labelling as above, and graph packings. 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. One application of the proposed research in graph searching is network security. Computer networks are often targeted by viruses (and worms, Trojan horses, etc.). Although one layer of security is provided by firewalls and antivirus software, all that is needed for the security of the entire network to be jeopardized is for one individual computer to be vulnerable, due to out of date antivirus software, for example. 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. 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. With regard to my work in graph packings, many problems of both practical and theoretical interest involve packing objects into a structure. For example, one might want to store as many radioactive containers as possible in a building without, say, any k containers being too near each other. This situation can be modelled via k-limited packings. This proposal considers 2-limited packings of complete grid graphs. Such graphs naturally arise in applications involving city planning and electrical circuit layouts.

一个图是一组顶点和一组边的集合，图是很好的模型。例如，我们可以用顶点来表示地图的区域，只要对应的区域共享一个非平凡的边界，两个顶点相邻，即由一条边连接。当打印地图时，期望最小化所需颜色的数量，使得共享边界的区域接收不同的颜色。在相应的图中，我们希望最小化颜色的数量，或者简单地说标签，需要以这样的方式给顶点着色，使得相邻的顶点接收不同的颜色。这是研究得很好的图着色问题。 在这个建议中，我们考虑一些图论问题。特别地，我们专注于三个领域：图搜索（Cops和Robber），图着色/标记如上所述，图包装。这里描述的研究计划有几个主题。例如，我们经常对研究所考虑的图的结构性质感兴趣。我从事这项研究的主要目标是推进图论领域的知识。除了保持加拿大在这样的数学研究的前沿，还有重大的实际应用的拟议研究计划。 所提出的研究在图搜索中的一个应用是网络安全。计算机网络经常成为病毒（以及蠕虫、特洛伊木马等）的目标。虽然防火墙和防病毒软件提供了一层安全性，但整个网络的安全性受到危害所需的只是一台计算机容易受到攻击，例如由于过时的防病毒软件。我在图搜索方面的研究着眼于通过开发有效的算法来解决网络安全中的这一弱点，这些算法旨在定位这些病毒，以便在感染网络之前对其进行隔离。其他应用包括刑事逮捕，建筑安全，跟踪蜂窝网络中的用户，以及解决与路由相关的电信问题。 除了在调度和资源分配的图形着色/标签的许多应用程序，我的工作在Skolem标签的一个应用程序是建模的通信网络的配置与一个中央集线器，将信息发送到网络的不同节点。关于我在图包装方面的工作，许多实际和理论上感兴趣的问题都涉及将对象包装成结构。例如，一个人可能想在一个建筑物中储存尽可能多的放射性容器，而没有任何k个容器彼此太近。这种情况可以通过k限制填充来模拟。这个建议考虑了完全格图的2-有限填充，这类图在城市规划和电路布局中很自然地出现。