Grant: Discovery Grants Program - Individual

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.