Some Problems in Graph Theory

图论中的一些问题

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

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