Investigations in graph theory

这个项目包括图论领域的两个问题。 第一个是网络搜索问题，称为“警察和强盗”，第二个涉及图中的独立控制。 随着我们越来越依赖互联网，设计有效的算法来遏制病毒和蠕虫已经变得至关重要。 网络追逃游戏如“警察与强盗”为此类算法的开发提供了良好的基础。 在“警察和强盗”的游戏中，一组“警察”在给定的网络上逮捕一个“强盗”。 警察和强盗轮流行动，总是知道对方的位置。虽然一个警察可以获胜的网络已经被完全描述，但对于那些需要两个或更多警察的网络却没有很好的描述。 然而，通过将给定的网络嵌入到其他高度结构化的网络中，已经获得了一些见解。或者相反，通过将网络分解为更小的网络，在这些网络上已知好的策略。 图的独立性、控制性和色数是图论研究中的基本问题。 我的第二个项目将这三个项目结合在一起。 一对不同的，但惊人的相似，结果发现在调查独立性导致一个问题之间的关系控制和色数。 对这种关系知之甚少，调查的可能性很多。

This project consists of two problems in the field of graph theory.  The first is a network searching problem called "Cops and Robber" and the second deals with Independent Domination in a graph.   With our increasing dependence on the internet, devising efficient algorithms for containing viruses and worms has become of vital importance.  Network pursuit-evasion games such as "Cops and Robber" provide a sound basis for the development of such algorithms.       In the game of "Cops and Robber", a set of "cops" works to apprehend a "robber" on a given network.  The cops and robber move in turn and are always aware of the other's position. While networks in which one cop can win have been completely characterized, there are no good characterizations for those that require two or more.  However, some insight has been gained by embedding given networks into other, highly structured networks. Or conversely, by decomposing the network into smaller networks on which good strategies are known.     The topics of independence, domination and chromatic number are absolutely fundamental in the study of graph theory.  My second project brings together all three.  A pair of distinct, yet amazingly similar, results found during investigations into independence leads to a question regarding the relationship between domination and chromatic number.  Little is known about this relationship and the possibilities for investigation are many.